First install Pandora by going to the Android Market. Then, on your home screen (or the screen you wish to have the widget display), click the menu button. Then, click Add. Next, select Widget. You then select Pandora (you may need to scroll down).

Note that there is an issue that causes the widget disappear and removes the option to install one. This happens if the app is installed to the SD card. For now, keep the app installed to the phone's local memory and the widget should work fine.