The gating factor will probably be Tioga Pass, which is Hwy 120 between Yosemite and Lee Vining. That road is closed in winter, and *typically* opens for Memorial Day, which is the last Monday in May. However, if there is a big snow year, it can open later.
Here's the historic dates:
http://www.nps.gov/yose/planyourvisit/tiogaopen.htmThere's a link to the plowing updates on that page, which will be useful next spring to keep an eye on the progress.
Next winter they are predicting a "La Nina" weather pattern, which is what they had last year, and might lead to extra snow in the mountains and a later opening date.
So, given all that, I would try to arrange your schedule so you were in Yosemite no earlier than Memorial Day, and ideally at least a week later, as you don't actually want to be there on the holiday, because it will be more crowded.
The other possibility is to get really lucky and time it so that you are there just before the road opens to cars, but after the plowing is complete. You can go through illegally with no cars.
Services in Tuolumne Meadows (up in the Yosemite high country, between Yos. and Lee Vining) will not be comletely open yet - camp grounds may be snowy/flooded, the store won't be open, you may need to filter water.
Other than that - in April and May you can get rain, which will be cold at the higher elevations. Be prepared for cold and rain, but you'll probably get more nice weather than bad.
I haven't done that trip yet, or planned it, but I would say early May is ideal, late April is OK, early/mid April is probably too early.
These guys started June 3rd and were too hot
http://www.crazyguyonabike.com/doc/?o=1r4vFZo&doc_id=6353&v=ZM