It only does receive and doesn't actually put the last character into the buffer until the next one is received, but it doesn't block!
http://telobot.com/downloads/nbserial.zip
For GPS, I'm using the SkyNav SKM53 ($30 on ebay, including shipping!) on a prototyping board from Radio Shack, cut down to Arduino size. It accommodates the GPS, tilt-compensated LSM303 Compass (SparkFun, with added 1.8v to 5v level shifters), L293D Motor Controller, as well as connections for several distance sensors and a quadrature rotary encoder. And, of course, the SPI WiFi.
The GPS works great, easily acquiring a signal at my indoor workbench, next to the EMI-noisy computer.
It is to make all these things work smoothly together that I'm interested in non-blocking libraries.
Next: a master-only, non-blocking TWI Wire library, and then I'll come back and pretty-up NBSerial.