Man, these answers are confused. Which is understandable, because this is complex, but quoting Wikipedia isn't going to do it. Here's my understanding, based on holding a diplomatic passport for 18 years and seeing all this first hand & up close.
So on a purely practical level, Doc's got it right: embassies and consulates are pretty much interchangeable from a traveller's view, as they normally both provide consular services like visas. All things being equal, it's usually better to deal with an embassy since they're usually larger and better resourced, and on occasion handle things that consulates don't. (There are exceptions, eg. sometimes embassies in awkwardly located capitals outsource visa processing to consulates in bigger cities, but this is rare.) When in doubt, check the website or give them a call.
On a legal level, let me try to straighten out the terminology a bit.
- An ambassador is a direct representative of a head of state to another country, which is why each country only has one.
- A consul is a representative of a government to another, and there can be many of these per country.
- An embassy is a permanent diplomatic mission (read: a delegation of diplomats) led by an ambassador. The term is often also used for the physical building they occupy, but that's more correctly termed a chancery.
- A consulate is a government delegation led by a consul. Likewise, the word is often used to describe the building itself.
- Consular services is the umbrella term for services provided to individuals: visas, passports, etc.
- A honorary consul is a local eminent person, often a citizen of the host country with business ties to the other, who has been granted (very) limited powers to provide consular services in a place that wouldn't otherwise have any.
- An honorary consulate is wherever said eminent person chooses to hang his or her fancy plaque on the wall. These are usually useless for day-to-day travel, since they generally have no regular opening hours or powers to issue visas, but they can be handy in an emergency (arrested, passport lost, etc).
In theory, the Vienna conventions try to divide the roles of diplomats and consuls, so that diplomats/embassies take care of state-to-state relations and consuls/consulates should handle the day-to-day grunt work of providing consular services. In practice, though, these roles are happily muddled; while consulates don't do state-to-state diplomacy, virtually all embassies handle consular services. Sometimes the embassy has a separate "consular section", which may even be in a different location, but it's still overseen by the ambassador and thus an integral part of the embassy.
Finally, having a full-fledged consulate without a corresponding embassy would be unusual in the extreme. (I know of one case, the Estonian consulate general in Sydney, and they're replacing that with an embassy in Canberra in 2015.) What's more common is that an ambassador is accredited to multiple countries, and the "sub"-countries without an embassy have honorary consulates.