Part 1 covered navigation links on main/category/archives pages. This post covers navigation links on single posts.
A: no navigation links on single posts
Almost Spring, Ambiru, Banana Smoothie, Beach, Benevolence, Blix, Chaos Theory, Chaotic Soul, Chunk, Comet [**], Connections, Contempt, Dusk, Emire, Fadtastic, Fjords 04, Fleur de Lys, Flower Power, Fresh Bananas, Girl in Green, Green Marinée, Greenery, Hemingway, Iceburgg, Jentri, Light, Misty Look [*], Monochrome, Motion, Neutra, Ocadia, Oulipo, Pool, Prologue, Quentin, Redoable Lite, Regulus, Rounded, Rubric, Shocking Blue Green, Silver is the New Black, Simpla, Solipsus, Supposedly Clean, Sweet Blossoms, Tarski, Thirteen, Titan, Toni, Treba, Twenty-eight Thirteen, Unsleepable, WordPress Classic.
[Update 2013: some of the above themes have been updated to include nav links.]
B: navigation links on single posts = titles of previous and next post
Albeo, Andrea, Andreas 09, Autofocus [**], Black-Letterhead, Bouquet, Brand New Day, Bueno, Choco, Clean Home, Coraline, Dark Wood, Day Dream, DePo Masthead [**], Digg 3 Column, Elegant Grunge, Enterprise, Fauna [**], Forever, Fresh & Clean, Freshy, Fruit Shake, Fusion, Garland, Greyzed, iNove, Inuit Types, iTheme2, K2-Lite, Koi [**], Kubrick, Liquorice, Misty Look [*], Mystique, Neat, Neo-Sapien, Notepad, NotesIL, Nuntius, Ocean Mist, Paperpunch, Parament, Piano Black, Pilcrow, Quintus, Reddle, Retro MacOS, Rusty Grunge, Sandbox (all four), Sapphire, Shaan, Spectrum, Splendio, Spring Loaded, Steira, Strange Little Town, Structure, Sunburn, Sundance, Sunspot, The Journalist v1.3, The Journalist v1.9, The Morning After, Toolbox, Triton Lite, Twenty Ten, Under the Influence, Vermilion Christmas [**], Vigilance, Vostok, White as Milk, Wu Wei, zBench.
[*] Misty Look: links optional (Appearance > Theme Options).
[**] Autofocus: plus “Older”, “Newer”, plus arrows. Comet: plus “Previous post”, “Next post”. DePo Masthead: plus “Before”, “After”. Fauna: plus “Home” tab. Koi: plus “Previous”, “Next”. Vermilion Christmas: titles accompanied by indication “Previous Entry:”, “Next Entry:”.
C: Isolated cases
Adventure Journal, Nishita: “Older post”, “Newer post”.
Andreas 04, Dusk to Dawn, Duster, Imbalance 2, Twenty Eleven: “Previous”, “Next”.
Blogum, Chateau, Esquire, Manifest, Matala, Pink Touch 2, Selecta, Skeptical, Suburbia: “Previous post”, “Next post”.
Bold Life: “Older Entry”, “Newer Entry”.
DePo Square: “Back to Home” plus “View more by category: […] Or by month: […] Or visit the complete archive”; same thing on static pages too.
Duotone, Modularity Lite, Monotone, Next Saturday: arrows.
Grid Focus: “Newer”, “Older”.
MLB (all three): “previous post”, “back to blog”, “next post”.
P2: “Older Posts”, “Newer Posts”.
Retro-fitted, Vertigo: “Older”, “Newer”.
wordpress tips 
Wow! what a heck of n undertaking that was. Thanks for all you do for your fellow wordpress.com bloggers. :)
Posted by timethief | March 17, 2010, 00:16Panos,
Nice. Thank you.
If I’d known that the theme I switched to last July didn’t have “next” “previous” “future” “past” “—>” “<—" links…
it might have been a 'deal-breaker' and I'd have stayed with Digg3 or tried VermillionChristmas or some other foolish theme.
LOL. Unsleepable it is. even with the mostly invisible bottom bar. Hope your custom formatting holds!
I am really surprised at how many themes do not have something so obviously basic (in my mind) as post-to-post navigation, though. Don't you thinK?
T
Posted by Tess | March 17, 2010, 03:46The lack of navigation links on single posts is a theme killer for me at WP.com — it’s one of the first things I look for. I have to wonder if some of these designers have ever really thought about how people wander through a site.
Anyway, great collation as always.
Posted by Dave Bonta | March 17, 2010, 05:19@Dave: Welcome here and thanks for the compliment!
Whether that lack is a “theme killer” depends on the nature of a particular blog, I think. When the content is such that a visitor is likely to browse through successive posts, then nav tabs on single posts are essential. In a blog like mine, in which a post may be completely unrelated to the next or the previous one, they’re unimportant.
@Tess: So I don’t necessarily consider them basic. But yes, I was also surprised to see them missing from so many themes.
By the way, checking themes for the previous/next tabs was your idea, wasn’t it? Or was it the Comments Off tab? (I’ve taken care of that too!) Or both?
But Vermilion Christmas? God forbid!
@timethief: Thanks! At least I’m more organized now. This started as merely noting down individual theme quirks. Then it evolved into checking one detail in all themes. But now I know better: I check several things together. The real nightmare is having to update so many posts each time a new theme is added…
Posted by Panos | March 17, 2010, 14:19Yes, for the previous/next certainly. Comments off? maybe: that was a long time ago…
Making Vermillion presentable, that would have taken a master of tricks for sure. Maybe not quite God though…
Posted by Tess | March 17, 2010, 16:46Would have taken a master of tricks and a less petty Matt, if you see what I mean…
Posted by Panos | March 18, 2010, 05:57indeed
Posted by Tess | March 18, 2010, 15:20The link to Part 1 is producing a 404.
Posted by timethief | March 22, 2010, 22:02Fixed – thanks!
Posted by Panos | March 22, 2010, 22:36