Hello,
Temp agencies have the same work authorization requirements as any other employer. Your fiancée should be able to work right off the bat with an EAD, as long as she also has a social security number/card. Keep in mind that she'll have to apply for another EAD after you get married, but in terms of what employers require, a valid EAD and social security card should do it. Fortunately, getting the social security card is pretty easy--you just go to the local social security office and show them ID (passport) and the visa. The card should arrive in a couple of weeks. You can apply for a SSN before you get married.
http://www.ssa.gov/immigration/ has more info. I think that the process has been streamlined recently, so you might be sent a social security card and not have to go to the office.
Julie