I haven't biked that exact route, although I've traveled in the area quite a lot (I work for SAP AG, which has its HQ right outside Heidelberg). FRA to Heidelberg isn't the most scenic area of Germany in which to bike, but it's not too bad. If it were me I'd take a train from FRA down to Freiburg in the Black Forest and then ride back to Frankfurt via the Rhine/Alsace area, through Strasbourg, and then up through the Mosel.
Lodging availability depends a lot on when you are traveling. You generally should not have problems finding "zimmers" (private rooms for let), Pensions or Hotels. During holiday periods, though it could be challenging, especially along the Mosel (the Trier to Koblenz section).
I have a personal Web page with general hints about lodging in Germany while bike touring that you might want to check out for more suggestions. http://www.brianwasson.com/trips/lodging.htm?ac
I also have a site that you might find useful about taking bikes on trains in Germany (and Austria). http://www.brianwasson.com/trips/trains.htm?ac
As another poster suggested, the tourist bureaus in each town can generally book lodging for you each night. You can usually find them by looking for a big, green lower-case "i" sign.
Germany and Austria are my favorite places to bike, hands-down. A great bike culture, very friendly to tourists, and with a great infrastructure to support touring.