First described by Boccaccio in his Decamerone, gnocchi are considered the first type of pasta ever made: a mixture of flour and water (the flour from wheat, millet, farro) shaped into round dumplings that were then cooked in boiling water.
The best-known version, made with potatoes, is fairly recent in historical terms, since potatoes did not become common in Italy until the 1800s. Gnocchi made with other main ingredients are common, like the small Sardinian malloreddus, made with semolina flour, knödel, made with stale bread (a day or two old), and gnocchi di ricotta1.
The strange-sounding word gnocchi traces its origin to the Latin term nucleus, from which nocchio, meaning gnarl, derived. In the dialect of the region around Venice nocchio became gnoco and from there it was an easy transition to gnocco and its plural gnocchi.
Potato gnocchi take time to make, but the result is well worth the effort. My recipe (derived by my mother's) is described here.
Update: this post describes potato gnocchi made with purple potatoes.
1 In this post I talk about a version of this dish.