For a 4th gen iPod shuffle, if you are using automatic syncing to sync the shuffle to a particular playlist (or more than one playlists) in iTunes, just remove the song from the playlist and sync the shuffle. This is the more convenient way to do it. For example, you can create a playlist called "iPod shuffle" in iTunes and put the songs for the shuffle on that playlist. Then, set the shuffle to sync to that playlist. When you add songs to or remove songs from that playlist in iTunes (iPod shuffle does NOT need to be connected), the next time you connect the shuffle, it will sync the changes made to the playlist automatically.
If you are manually adding songs to the shuffle, connect shuffle, and select it in the iTunes sidebar (under DEVICES). Click the little triangle (next to the shuffle's name) to see the shuffle's contents, and select Music (under the shuffle's name). Over to the right, select the song or songs you want to delete and press the Delete key on keyboard.