If it's just a playlist you deleted then your songs will still be in iTunes. If you're talking about restoring the actual playlist then you can't as the undo button is greyed out.
Stay tuned, hopefully someone else will have a solution. So far I created 2 playlists and deleted both and the undo button stays greyed out and I couldn't recover them.