in Germany rejected asylum seekers are asked to leave the country within a certain space of time. In this period of time they have no permission to work.
If for some reason they do not leave Germany and cannot be deported, they will get the "Duldung", which is not an Aufenthaltstitel, but allows you to be present in Germany as long as your deportation cannot take place.
If you hold a Duldung for a certain time, you can ask the Ausländerbehörde for a work permit. Under certain conditions they can give you permission to work. But it certainly is not as easy as it sounds in your question.