'A cup of Joe,' as a reference to a cup of coffee, first appeared as popular slang in the 1930s and 40s. Opinions differ on where this phrase originates from, but presented here are a few different theories.

Something to do with the Military?

In 1914, the secretary of the US Navy, Admiral Josephus 'Joe' Daniels abolished the officers' wine mess. From that time on the strongest (and apparently therefore the drink of choice) on board navy ships was coffee. It was dubbed 'a cup of Joe' after the secretary.

'A cup of Joe' also refers to the GIs' favourite drink. During World War II the US defence workers were supplied with as much coffee as they wanted. Coffee was a source of warmth and comfort for battle-weary troups.
The slang was popular enough to be included in the Reserve Officer's Manual of 1931.
A variation on this theme has it that Joe refers to the average Joe, thus making 'a cup of Joe' the average drink of the average man.

Martinson's Coffee

There was a New York company named Martinson's Coffee (Andy Warhol liked to paint the cans) owned by a man named Joe Martinson. The neighbourhood of the company would be saturated by the aroma of roasting coffee, and coffee therefore became known as 'a cup of Joe'.
It sounds lovely, the thought of waking every morning to the smell of newly-roasted coffee beans, but actually it's not. Take a trip through a town with a company that roasts coffee - for example Karlstad in Sweden - and you'll understand. If the neighbourhood said anything they likely said 'a smell of Joe' and meant it in a negative way.

How drunk do you have to be to mispronounce Java?

'Joe' is a derivation of 'Java'. Java itself became a popular American nickname for coffee in the 19th Century when the island of Java in Indonesia was a major source of the world's coffee.

Old Black Joe

Yet another theory connects 'a cup of Joe' to the song 'Old Black Joe', written by Stephen Collins Foster (author of 'Oh! Susannah' and 'Camptown Races') in 1860. Of course, if you read the lyrics you'll find they have nothing to do with coffee:

Gone are the days when my heart was young and gay,
Gone are my friends from the cotton fields away,
Gone from the earth to a better land I know,
I hear their gentle voices calling Old Black Joe.

I'm coming, I'm coming, for my head is bending low,
I hear their gentle voices calling Old Black Joe.
Why do I weep, when my heart should feel no pain,
Why do I sigh that my friends come not again?
Grieving for forms now departed long ago.
I hear their gentle voices calling Old Black Joe.

Where are the hearts once so happy and so free?
The children so dear that I held upon my knee?
Gone to the shore where my soul has longed to go,
I hear their gentle voices calling Old Black Joe.

So Which Is Correct?

The most prevalent theory of the origin of 'a cup of Joe' is the one that concerns Josephus Daniels. It's the one you'll hear on the History Channel (if you're in North America) and is the one you'll find in columns exploring the origins of words and phrases. It's widely repeated on the Internet (often word by word as if people were copying and pasting).