I think if you go into MP, select Shuffle All Songs and then exit out to the desktop, the Media Player Widget will remember shuffle-all mode as your preference and continue to use it when you press the play/pause button.

That seems to be the case on mine at least.. I just tap play and then the FMTX widget and it's all set (and the new version of FMTX that incorporates boost is a massive win)