Well done! Thank you for all of your replies; there were more than I could reply to personally due to a PM limit (spam filter!) at RHP. The First Responders were:
robbebop (1588)
vandervelde (2116)
Eladar (1499
thaughbaer (1779)
HikaruShindo (1661)
krieghoff (2421)
I suppose krieghoff and vandervelde saw this instantly. For the rest of us no-where-near-IM-level duffers, I offer the following explanation, what my thought process was in solving this.
The puzzle intrigued me because it is an example of Emanuel Lasker's remark that when you see a good move, wait, keep looking because you might find something better. My first instinct, and maybe yours too, was to promote the b-pawn to a queen. Black then plays Ka6 and will be mated, eventually, but not on the next move.
So, I had to think again, harder, and under-promote (an interesting topic in itself).
At this point, I stopped thinking about what White could move and started thinking about Black instead. The Black K is very nearly stalemated already: he has only one legal square left, a6. Take away a6, and any check will be checkmate. Under-promoting to a N on b8 would take away a6 from the Black K; now a quick look is needed to ensure that Black still has a legal move if a N is on b8 — we don't want to stalemate him. Yes, Black can still play a7-a6 — as krieghoff noted above, forced. This is good, because it traps the Black K, and now any check at all will be checkmate.
From here, it is a short hop to seeing that Nxc6 is mate.