Depending on where you are, there's a range of maps around.
Kompass (
www.kompass.at) publish good walking/cycling specific maps (with recommended/marked routes), mainly of the mountain and touristy areas, but coverage is increasing (I think they're planning to cover the whole country at some point) - scale is usually 1:40,000.
There's also the "official" (Topographische Karten or TK) map series, which I think vary a little by Bundesland - here in Mecklenburg they're available in 1:10,000 (TK10), 1:25,000 (TK25), 1:50,000 and 1:100,000. They don't have all the useful information for walkers/cyclists/tourists that the OS maps have, and are often quite out of date, particularly in rural areas (10 years old seems to not be uncommon, even in places where there's big changes like new motorways), but do have complete coverage. Good bookshops usually stock the local maps, or you can try and track down the local Landesvermessungsamt (name varies by Bundesland!) who can probably do mail-order. Cost is usually about 5€/sheet.
There's often also a range of other local maps showing marked cycle routes, walking routes, tourist areas and the like (and ADAC maps often), but the quality of these varies enormously.
The "MagicMaps" mentioned by Nicole supply the TK25. The software isn't fantastic, but it is usable, and considering you get a lot of sheets worth of TK25 then it's good value for money (and it means you can print out your map and it doesn't matter if it gets wet and trashed while out walking) - go for the newer DVD version if you've got a DVD reader on your computer as they have higher-resolution maps and the latest data (although still as out-of-date as the paper maps). Amazon.de also stock the MagicMaps, and since it's above the free postage limit you save the postage that MagicMaps themselves charge.
(note that my info applies here in MV - since every Bundesland has it's own version of the OS then it's a bit haphazard!)