You do need an emission sticker for the inner parts of both cities. Here are links to maps showing the zone for Düsseldorf and Cologne (Köln) to see if your destination is part of the zone. If these links become invalid, just use Google's picture search for "Umweltzone [name of city]" and you should get decent results.
First I'd ask the car rental company beforehand whether they have cars which got the sticker already. If that's not the case, you'll have to buy one yourself (~ 5 Euros)
You can get the sticker at one of the official inspection authorities. These are named DEKRA, GTÜ, TÜV and KÜS. My suggestion would be to search Google Maps for these and choose one that is conveniently on your planned route. They're usually in industrial areas of towns. Mind the opening times, and make sure you know where the car's registration documents are. It should only take a few minutes on location.