Is this your first time using a computer? Have you ever heard of "Edit -> Delete" or right-click and select delete? Do that in iTunes and then resync to get rid of it on your iPod too.
File -> New Playlist works for me in iTunes. If you're doing it from your iPod Touch, there's controls there for new/edit playlists under the playlist menu sub-heading.