It could be one of three things:

1) Your venue(s) might not have been added correctly into the Foursquare database just yet. To add you venue, go here: http://foursquare.com/add_venue

2) Be sure to search at Foursquare.com/search, not Explore - Explore is designed mainly as a recommendation engine, not a search tool.

3) Venue search is not universal, so you will only see venues in your area. To change the search area, you can also input a city to search near on the page that returns your search results: