I've recently released the Tinyserial library - a library that provides basic polling-based serial I/O functions for Diecimilla and Duemilanove boards, including support for storing constant strings in Flash to save SRAM.
Although the Tinyserial library provides far fewer features than the interrupt-driven ones that ship in the Arduino software distribution, it also uses far less Flash and SRAM, leaving more for your applications.
It's written in assembly, but respects the GNU libc ABI, so you can call into it from C and C++ programs. (OK, so maybe this was simply an excuse to code in assembly for the first time in 20 years... 
)
More info and source download under LGPL:
http://alum.wpi.edu/~tfraser/Software/Arduino/tinyserial.html