Printing under Linux has been and continues to be problematic. After switching print daemons multiple times Linux seems to have settled on using the Common Unix Printing System (CUPS) which is a good thing as CUPS is very flexible and should be easy to use. However there are problems and after the upgrade from Fedora 10 to Fedora 11 it was a struggle for me to get printing working reliably again.
Many printers print quite reliably when you plug them in; no additional work is required. Some printers require a bit of fussing and some will never work at all. Many Lexmark printers fall into this last category. HP printers are generally well supported and work just fine although some may require a modicum of fussing.
This section of the DataBook® for Linux Administrators covers printing configuration and especially using CUPS.