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”.