I recently read a very good introduction to octopus keeping by
Rob Toonen for Advanced Aquariasts Online Magazine in 2003 that I will recommend reading as you start your research.
At the moment there are five species in aquariums for US TONMO members and two others that we have seen in the last several years. The tank recommendations are approximate minimums and different keepers will give somewhat different numbers. In order of size (and hence tank requirements), largest to smallest they are:
Octopus
vulgaris - Crepuscalar - Caribbean - 130+ gallons
Octopus
briareus - Crepuscalar - Caribbean - 65+ gallons
Octopus
bimaculoides - Diurnal - West Coast Pacific - 50+ gallons
Octopus
hummelincki - Diurnal - Caribbean - 50+ gallons*
Abdopus
aculeatus - Diurnal - Indonesia - 45+ gallons
Macropus sp - Indonesia - Nocturnal - Indonesia - 45+ gallons
Octopus
mercatoris - Nocturnal - Caribbean - 20+ gallons
*The hummelincki varies the most in sizing and we have seen some that grow no larger than a large dwarf and other that are the size of a small bimac. There is very little research on this species available to the general public (or possibly at all) so it is unknown if this is a single species or two different species with the same label.
As CaptFish mentions, the stickies at the top of the Journals and Photos forum contain lists of our octopuses (and cuttles) by year. From 2008-2010 the lists have links to the individual journals of the animals.
The Tank Talk forum is full of discussion on building out a tank and octoproofing a cover (not needed for cuttles).
There is no "beginner" species. Ordering an octopus is not straight forward. Few suppliers know the species they have available so you will see them listed as "Bali", "Common Brown", "Common" or "Common Caribbean". Most times, these are meaningless. Sometimes "Bali" will refer to an A.
aculeatus. Sometimes Common Caribbean refers to O. briareus (common name is Common Caribbean Octopus). The official common name Common Octopus refers to O.
vulgaris but that is almost never the case when it is listed. Sometimes you will see "Caribbean Bimac" or bimac and can determine it was caught in the Caribbean and it will be a hummelincki. Collection for resale of the bimacs is illegal in California and the majority of this species is found along its coast (there are some in Mexico but we don't see octopuses from Mexico imported).
There are a few suppliers that will ship the same species MOST of the time. Live Aquaria will USUALLY ship A.aculeatus as its Indonesian octopus (however, often enough to make note, it is a small nocturnal Macropus). Tom's Tropicals will USUALLY ship O. briareus as O. briareus but a hummelincki (maybe) and two vulgaris have slipped in there this year. When saltwaterfish.com have octopuses, they are USUALLY hummelincki from Haiti. Reading the availability thread will help you get a general idea.
Because of the difficulty determining species and the short lives of these animals, we recommend building out a minimum of a 55 gallon tank (and a 65 will accomodate one more species).