Currently they say they have over 200,000 titles available. But they've partnered with all 5 big labels, so I'd imagine that there will be a lot more titles to come.

I'd imagine that if you were wanting to try iTunes4 out, you could stop by your local apple retailer (or Apple Store if you have one close by) and search around their song title database all you want.