The trick is to rename the file to .ppt, after which Keynote will instantly recognize them.
[robg adds: If you have Office for OS X installed, it should open .pps files just fine, unless they were encrypted on the Windows machine -- in that case, you'll have to ask for an unprotected version of the slideshow, as Office for OS X can't handle protected Office for Windows documents (a glaring oversight in the cross-platform compatibility arena, if you ask me).]

