This KB Article refers specifically to iTunes
Q: My podcast was just approved but I can't find it when I search the Store. What happened?
A: Podcasts are accessible via their podcast URL just a few minutes after they have been approved for inclusion in the iTunes Store. However, it can take 24-36 hours for the podcast's data to make it into the iTunes search index. So if you can't find your podcast yet, be patient: you will be able to find it by title, author, and description (and to a lesser extent, keyword) after the next update of the search index.
