If you are playing songs using iTunes' new Party Shuffle playlist, just control-click any song in your iTunes library and select "Play Next in Party Shuffle". The song will appear in Party Shuffle next to the song currently playing.
[robg adds: I don't normally run contextual menu hints, but this one is very useful and very easy to overlook -- I know I hadn't noticed it yet.]
Mac OS X Hints
http://hints.macworld.com/article.php?story=20040830035448525