Jon, I think you are talking about the unweltplakette, which are environmental stickers (green, yellow or red) awarded in accordance to the manufacture performance of your car in terms of exhaustion pollution. Any passenger car manufactured post-2009 (thus any rental car on current fleets of rental agencies) can get a green sticker and thus drive anywhere.
There is no test to be made on your car, they just take the car registration document, look upon the standardized pollution info on it (according to EU rules) and give you a sticker. It costs something like € 8 and is valid nationwide forever (until the car is disposed of).
You can buy such environmental sticker from some gas stations and car shops. It usually takes 5 minutes for you to take your car registration title, have a clerk find the pollution index on it, check on a database/table and give you a sticker.
Read all about it here: http://www.umwelt-plakette.de/englis_informations.php