I'll take some example from my remake. Be warned that some of these may contain solution spoilers, and in at least one case the name of one contains a spoiler for the solution to another!
"Dude, Where's My Exit?" and "Retreat!!!" - Pretty self-explanatory names, especially once you see the levels.
"Star Unit 16"/"Star Unit 17" - Well, I thought the level kinda looked like a starship or something...
"Remember Where You Find Them!" - This is a hint for the solution to the harder version of this level.
"The Ultimate Answer" - 42 is supposedly the answer to life, the universe, and everything... and in terms of skills and stats, this is basically the 42 version of All The 6's...
"Lemmings on a Plane" - A reference to Snakes on a Plane
"Annyeonghaseyo Lemming-Nim" - More or less the Korean equivalent of "Konbanwa Lemming-San"... similar, anyway.
"One Day,One Lem" - Reference to the song "One Day,One Dream" by Takki&Tsubasa. I was probably listening to it at the time.
"Don't go there just yet..." - An obscure hint to the solution, in that you can't go to the exit right away but must go past it and do something else first.
"YOUR LEM A SPLODE" - A reference to the meme "YOUR HEAD A SPLODE"
"Nuclear Lemmings" - Explosions. 'nuff said.
"Do A Barrel Roll!""Tribute To Timfoxxxy" - In my opinion at least, his levels were at least semi-good-looking, but in terms of the actual solution, were almost nothing but build build build with a blocker holding the majority back... so I exaggerated this a bit...
"Randomly Insane Lemmings" - A reference to the Random Insanity message board on GameFAQs
"All or Nothing: The Revenge" - It's the same idea. Hope you get the right direction when you bash.
"As Complicated As It Looks" - It's the same level except with the time limit increased and the window and exit moved, so I thought it was fitting to change the name as little as possible. And I did so, and at the same time gave it a much more accurate name for the new version.
"Speed Freaks" - The basic idea is clickclickclick as fast as you can.
"We're Not The First Ones Here" - Well, since the level is mostly already solved AND the exit is blocked off...
"Chain Reaction" - A very very very terrible pun. But it's better than all those snow jokes.
"Explore The Unknown" - A blatantly obvious hint to the solution. If you realise it's a hint, that is.
"Double Your Lemmings" - If you don't work out the trick, it almost seems as if you have to duplicate a lemming to solve this one.
"Lemming Crossover" - Comes from that the lemming who solves for the left side comes from the right, and vice versa. But not nessecerially in that order.
"The Diving Board" - Well, it looks like one. And your lemmings are pretty much going to take a dive here, unless you're very clever and quick.
"When Hell Freezes Over..." - Just thought I'd let you know when you're likely to solve this level. ^^
"Pipeline Problem" - Well. There's pipes, and there's problems. Is that enough for you? ^^
Some other names have meanings or points to them that I can't be bothered mentioning, either because they're blatantly obvious or I just can't. Most of them, however, are completely random.