There are roughly three kinds of sushi: nare-zushi, namanari-zushi and haya-zushi. Considering these will provide an overview of the history of sushi.
While sushi is considered to be one of the most representative foods of Japan today, it actually originated in China at the end of 2nd century A.D. It began as salted fish meat fermented in unpolished or polished rice. At that time, only the fish was eaten and the rice was discarded. This type of sushi is called nare-zushi in Japan. Its fermenting time could be as long as 1 to 3 years.
During the 15th centry, namanari-zushi was developed. It was not fermented as long as nare-zushi. After one month's fermentation, the fish was still more or less raw. However, as well as being preserved, its flavour was mellowed as a result of the fermentation. And for the first time, the rice was eaten along with the fish.
In the 16th centry, sake-zushi, bara-zushi and saba-zushi was developed. These are still namanari-zushi. Sake-zushi was made for those who wanted to view the cherry blossoms in spring. It used sweet rice wine and some pink colouring mixed into the rice. Bara-zushi was made for the Spring Festival. Both sake-zushi and bara-zushi resemble today's chirashi-zushi. Fish, shellfish and vegetables were layered with rice alternately. Saba-zushi is mackerel marinated in vinegar. Then, rolled with rice in a cloth by hand. This would much later lead to different types of sushi -- those rolled into maki in bamboo mats or hand formed (nigiri-zushi).
In the middle of 17th centry, su or rice vinegar was first used in sushi making in order to shorten the fermentation time and enrich the flavour of sushi. This is the beginning of the Haya-zushi or box sushi. This is also called Osaka-zushi, because it was developed in this period of time in Osaka city. "Hako" means box in Japanese. Hako-zushi is sliced and salted fish packed with vinegared rice in a wooden box with a stone weight placed on it. After one night's fermentation, it is sliced into rectangles and eaten that same day. Hako-zushi is still very popular in Japan today but is very well not known elsewhere. Which is very very sad for everyone elsewhere. Oh well.
In the early 19th century, in Edo, now called Tokyo, nigiri-zushi was developed. Nigiri-zushi was also the most important innovation in haya-zushi since the 17th century. It completely changed the traditional image of sushi. Nigiri-zushi is the popular hand-formed sushi seen in restuarants outside of Japan. It is simply a delicately sliced piece of the best quality and freshest fish, moulded atop lightly vinegared rice, with a dab of wasabi to hold it in place.
Before Nigiri-zushi was developed, norimaki-zushi appeared in the end of 18th centry. These are the maki or rolls (such as kappa-maki) which are common in restaurants. This method uses a bamboo mat to press the fish and rice together within a sheet of nori rather than a stone weight to press the ingredients together.
Here's a glossary that might be useful.
aji -- horse mackerel
akagai -- ark shell
ama-ebi -- raw shrimp
anago -- conger eel
aoyagi -- round clam
awabi -- abalone
ayu -- sweetfish
buri -- adult yellowtail
chutoro -- marbled (with fat) tuna belly
ebi -- boiled shrimp
hamachi -- young yellowtail
hamaguri -- clam
hamo -- pike conger; sea eel
hatahata -- sandfish
hikari-mono -- various kinds of "shiny" ("oily") fish, such as mackerel
himo -- the "fringe" around an ark shell
hirame -- flounder
hokkigai -- surf clam
hotategai -- scallop
ika -- squid
ikura -- salmon roe
inada -- very young yellowtail
kaibashira -- eye of scallop or shellfish valve muscles
kaiware -- daikon-radish sprouts
kajiki -- swordfish
kani -- crab
kanpachi -- very young yellowtail
karei -- flatfish
katsuo -- bonito
kazunoko -- herring roe
kohada -- gizzard shad
kuruma-ebi -- prawn
maguro -- tuna
makajiki -- blue marlin
masu -- trout
meji (maguro) -- young tuna
mekajiki -- swordfish
mirugai -- surf clam
negi-toro -- tuna belly with chopped scallions
ni-ika -- squid simmered in a shoyu-flavored stock
nori-tama -- sweetened egg wrapped in dried seaweed
Otoro -- fatty portion of tuna belly
saba -- mackerel
sake -- salmon
sawara -- Spanish mackerel
sayori -- (springtime) halfbeak
seigo -- young sea bass
shako -- mantis shrimp
shima-aji -- another kind of aji
shime-saba -- marinated mackerel
shiromi -- seasonal "white meat" fish
suzuki -- sea bass
tai -- sea bream
tairagai -- razor-shell clam
tako -- octopus
tamago -- sweet egg custard or an omelette wrapped in dried seaweed
torigai -- cockle
toro -- choice cut of tuna belly
tsubugai -- Japanese "tsubugai" shellfish
uni -- sea urchin roe
Maki-zushi (sushi rolls)
maki-mono -- vinegared rice and fish (or other ingredients) rolled in nori seaweed
tekka-maki -- tuna-filled maki-zushi
kappa-maki -- cucumber-filled maki-zushi
tekkappa-maki -- selection of both tuna and cucumber rolls
oshinko-maki -- -pickled-daikon (radish) rolls
kaiware-maki -- daikon-sprout roll
umejiso-maki -- Japanese ume plum (really more like an apricot, but the convention is to call it a plum)and shiso-leaf roll
negitoro-maki -- scallion-and-tuna roll
chutoro-maki (the "u" is long) -- marbled-tuna roll
otoro-maki (the first "o" is long) -- fatty-tuna roll
kanpyo-maki -- pickled-gourd rolls
futo-maki -- a big fat roll filled with rice, sweetened cooked egg, pickled gourd, and bits of vegetables
nori-maki -- same as kanpyo-maki; in Osaka, same as futo-maki
natto-maki -- sticky, strongly flavoured (and uh... aromatic) fermented-soybean rolls
ana-kyu-maki (the "u" in "kyu" is long)-- conger eel-and-cucumber rolls
temaki -- hand-rolled cones made from dried seaweed
maguro-temaki -- tuna temaki
Some Other sushi terms
nigiri(-zushi) -- pieces of raw fish over vinegared rice balls
Edomae-zushi -- same as nigiri-zushi; "Edo" style
chirashi(-zushi) -- assorted raw fish and vegetables scattered over vinegared rice
tekka-don -- pieces of raw tuna over rice
sashimi -- slivers of raw fish (without rice)
chakin-zushi -- vinegared rice wrapped in a thin egg crepe
inari-zushi -- vinegared rice and vegetables wrapped in a bag of deep-fried tofu
oshi-zushi -- Osaka-style sushi: squares of rice pressed in a mold topped with vinegared and/or cooked fish
battera(-zushi) -- oshi-zushi topped just with mackerel
-tataki -- pounded, almost raw fish
odori-ebi -- live ("dancing") shrimp Ack!
oshinko -- Japanese pickles
neta -- whatever is on top of sushi
wasabi -- Japanese horseradish
gari -- pickled ginger
shoyu -- soya sauce
Addendum
There are a vast number of other modern maki (rolls). California Roll, even a Texas Roll. But I don't know anything about them. I am informed by Magenta that some places from Hong Kong to the U.S.A. also serve unagi-maki, a nori roll with grilled eel. But I have never encountered these either.