You need to save your playlists. And save them where ever you choose. See the lower part of this thread which discusses playlists: How to transfer music to my iPod (& iTunes)
Also remember that a playlist is simply a file with a list of songs that point to the location of the mp3. So if you move the song after you created the playlist, then the playlist won't work.