Do you create newsworthy shows? Apply for inclusion in Google News.
Some podcasts hosts (like LibSyn) allow you to turn your podcast into an app dedicated to your podcast. This can help people find you via the iTunes and Google app stores.
Make business cards. Good ones — like, Moo good. You never know when you'll meet a potential listener, advertiser or sponsor. A card is the best way to help someone find you after a meetup, flight, trade show, etc.
Spread infectious enthusiasm
Offer to speak at a Meetup. If you travel, offer to speak at Meetup groups in cities that you visit. Create your own Meetup related to the topic of your podcast.
Join LinkedIn groups related to your podcast topic. Check in regularly and contribute to conversations. Try to resist plugging your podcast, except when a link to an episode would be a legitimately-helpful resource.
Put out episodes regularly. One per week (or more) is ideal, but one every two weeks is fine — consistency trumps all.
Make your podcast title more discoverable with keywords. Bad: "Close Call". Good: "Close Call – Funny Phone Calls with Our Neighbors".
Make episode titles descriptive instead of "cute". They're an opportunity to use keywords that you want to be associated with your podcast.
Create a community around your podcast's topic. Ideally, do this as a forum on your site so your podcast's domain reaps the benefit as Google juice.
Create a page for your podcast on Facebook. Or better, if your podcast lends itself to community discussions create a Facebook group.