I think you are right in suspecting that the printer is likely the largest source of color error. Also, from your description of the error it seems to be just a color cast issue as opposed to this green color necessarily being out of the gamut of your printer. Which printer are you using? Here's some example color gamuts for printers ([COLOR=DimGray]gray) compared to sRGB ([COLOR=White]white) and Adobe RGB 1998 ([COLOR=Black]black)
left: fuji frontier (typical walmart/costco/etc printer), right: high-end inkjet printer
(both at 50% luminance for comparison)
There are two ways to go about solving this color problem: (i) the systematic color profiling option or (ii) the quick and dirty guess and check method. If you just need OK results quickly, then the crude guess and check method might be satisfactory. Try experimenting with different combinations of default/manufacturer color profiles for your printer (if available), along with a few different types of paper for each profile tested (sounds like a likely cause in you case). Sometimes you can also find non-manufacturer profiles for your printer on the internet with a quick search.
If you need more accurate results, ultimately the best thing to do when serious about using a particular printer (and something I always do) is to have a custom color profile made. This typically runs $30-50 if you want to have it professionally done, and has to be performed separately for each type of paper you intend to use. It will nearly always produce superb color and black and white prints, even on lower end printers. Do a quick search for "printer custom color profile" and you will find several good options. You will need to print out one of their standard color targets on each paper you intend to use, mail these to them, and most will send you back the printer color profile(s) by email.
If you are performing editing on your computer and want fine color control, having your monitor profiled is also very important, but from your description it seems like your large color deviation is less from the monitor than it is from the printer. A hardware monitor calibration device typically runs around $200-300 for a model that should be fine for your purposes. A couple that come to mind are the ColorVision Spyder or GretagMacBeth Eye-One Display. More expensive hardware calibration devices can also create printer color profiles, however these are often much more expensive, produce inferior results and are primarily useful when you have many, many different paper/printer combinations to profile.