One understands that there are infinities of polyhedra; thus it is unrealistic to want to name them all... Nevertheless since a long time names, sometimes complicated ones but always following a certain logic, have been given the best known of them and to certain types or families of polyhedra with interesting properties.
The first idea was naming a polyhedron according to its number of faces by using the Greek root hedron (seat, base) with numerical prefixes:4 tétra 5 penta 6 hexa 
7 hepta 8 octa 9 ennéa 
10 déca 11 hendéca 12 dodéca 
14 tétrakaïdéca 20 ico 24 icotétra 
30 triaconta 60 hexaconta 100 hecato 
The prefix rhombi indicates that the planes of the 12 (resp. 30) square faces are those of a rhombic dodecahedron (resp. rhombic triacontahedron): four Archimedean polyhedra, the small rhombihexahedron . . .
There is no rule for the use of anti: antiprisms, anticube . . .
hemi is used to indicate that faces go through the centre: cubohemioctahedron, rhombic dodecahemioctahedron . . .
The snub operation introduces "rings" of new faces around the existing faces: two triangles for each edge, and an xgon for each xvertex; in this way the snub cube is also the snub octahedron. Each face of the "expanded" polyhedron is rotated by the same angle and in the same direction, thus this leads to two enantiomorph polyhedra (mirror images) depending on the rotation's direction.
The nkis operator introduces a new vertex on the axis of each nface, and therefore n triangles (in fact each xface is augmented with a xpyramid); so the tetrakiscube has 6x4=24 triangular faces, thus is an icositetrahedron.
A compound polyhedron is the union of several identical or related polyhedra arranged to preserve a polyhedral symmetry: the anticube is a compound of two regular tetrahedra, my favourite is the compound of five regular tetrahedra.
A few names refer to the discoverer: lord Kelvin's (truncated octahedron) or Romé de l'Isle's (rhombic triacontahedron) polyhedron, Kepler' star (stellated octahedron), Kepler's hedgehog (great stellated dodecahedron), Poinsot' star (great dodecahedron) . . .
The names of the Johnson's polyhedra and uniform polyhedra use a more varied vocabulary: (gyro)elongated, (tri)augmented, para/metabiaugmented, gyro/orthocupola or rotunda ...
Crystallographers use a different vocabulary for certain crystal forms.
Schläfli's symbols like {p,q} allow to describe regular polyhedra: q pgons around each vertex.
examples: {4,3} designates the cube and {5/2,5} the small stellated dodecahedron.
For the Archimedeans and the uniform polyhedra letters are used to indicate transformations: t for truncated, s for snub . . .
examples: t{3,4} designates the truncated octahedron and s{5,3} the snub dodecahedron.
The more complex Wythoff's symbols are used to describe the uniform polyhedra. A polyhedral kaleidoscope (three mirrors building a trihedron) is associated to a spherical triangle defined by central projection of a face on a sphere centred on the common point of the symmetry axes. The polyhedron's vertices are the images by the kaleidoscope of a particular point P of the spherical triangle with angles π/p, π/q and π/r (p, q and r rational); then the symbol depends of P:
pqr, pqr, pqr or pqr.
examples: 5  2 3 designates the regular icosahedron, 2 5  3 the truncated icosahedron,  2 3 4 the snub cube, 4/3 3 4  the cubohemioctahedron and 2  5/2 5 the dodecadodecahedron.
John Conway proposed a nifty notation, simple and efficient, which not only allows to describe many polyhedra, but which is also a tool to conceive new ones. At the start one chooses an elementary polyhedron denoted by a capital letter; each transformation is specified with a lowercase letter before the notation of the preceding step.
As starting polyhedron one may choose one of the regular polyhedra T, C, O, D or I, a regular prism Pn, a regular antiprism An or a regular pyramid Yn (with n ≥ 3 for the base's ngon). Let us notice that P4=C, A3=O and Y3=T.
John Conway defined eleven operators, and George W. Hart added three (the last three):
d  change to the dual (each face becomes a vertex and each vertex becomes a face): ddX=X 
t or tn  truncate is the truncation of all vertices: the face's orders are doubled, at each xvertex an xface is created
tn is the truncation reduced to the nvertices examples: t5dA5=D, tnYn=Pn (for n>3) 
a  ambo is the truncation through the mid points of the edges: the ,midpoint of each edge becomes a 4vertex aX=adX
examples: aC=aO is the cuboctahedron, aI=aD is the icosidodecahedron, aT=O, aYn=An 
k or kn  kis creates a new vertex on the axis of each face and replaces each xface by x triangles
kis and truncate are conjugated by duality: kX=dtdX example: kC is the kiscube or tetrakishexahedron 
j  join (dual of ambo: jX=daX) creates a 4face to replace each edge (it's k with the triangles coplanar by pairs)
examples: jC=jO is the rhombic dodecahedron, jD=jI is the rhombic triacontahedron, jT=C 
e  expand "expands" the polyhedron: a rectangle is created to replace each edge and an xface on each xvertex
eX=aaX and eX=edX examples: eC=eO is the small rhombicuboctahedron, eI=eD is the small rhombicosidodecahedron 
s  snub creates "rings" of faces around the existent faces: two triangles for each edge, and an xgone for each xvertex.
All the vertices of sX are of order 5. sX=sdX has no symmetry planes. sT=I 
g  gyro is dual to snub: gX=dsdX=dsX has no symmetry planes and all its faces are pentagonal
g is related to k, but a new edge is connected to the third of an existent edge (Z distorted) example: the gyrododecahedron gD=gI is the pentagonal hexecontahedron, gT=D 
b  bevel is defined by bX=taX =bdX example: bD is the great rhombicosidodecahedron 
o  ortho is dual to expand : oX=dedX=deX=jjX example: oD is the deltoidal hexecontahedron
o may be related to k, but a new edge is connected to the midpoint of an existent edge (V distorted) 
m  meta is dual to bevel : mX=dbdX=dbX=jkX and mX=mdX
m appears as a combination of k and o (with the two types of new edges) 
r (Hart)  reflect (mirror image) exchanges the enantiomorph forms of a chiral polyhedron 
p (Hart)  propellor creates n quadrilaterals around each nface example: pT is the tetrahedrally stellated icosahedron
p is selfdual pX=dpdX and pdX=dpX, and it commutes with a (pa=ap), j and e 
c (Hart)  canonic transforms a convex polyhedron in its canonical form 
Only s and g reduce the group of symmetries of the polyhedron which they transform (the symmetry planes disappear).
Let's notice that this notation specifies only the topology of the polyhedron, not its geometry.
Here are examples of "nice" polyhedra created using Conway's notation and a program by Hart for a convenient geometric realization.
George W. Hart's algorithm allows today to generate easily polyhedra with several thousands of faces in a few dozens of seconds; unfortunately only an old version 4.8 of Netscape with a VRML plugin displays the created VRML file (the pleasure to create quickly outstanding polyhedra is worth installing this old browser).
stI=dgkD (272 faces) and its dual (180 faces) 
sdk5sI=dgk5dgD (632 faces) and its dual (420 faces) 



two enneacontahedra (90 faces, 92 vertices, 180 edges)
jtI=jkD=dakD and jtD=jkI=dakI 
eptI=aapdkD (902 faces, 900 vertices, 1800 edges) 
references: 
• works of Kepler, Catalan ..., the two books by Magnus J. Wenninger: Polyhedron Models (pages 410) and Dual Models
• pages from the site Virtual Polyhedra: polyhedra generator (Conway's notation) and sculptures by George W. Hart • Naming polygons and polyhedra by John Conway • Visualization of Conway Polyhedron Notation by Hidetoshi Nonaka • a Java applet by Bob Allanson to visualize a few classical transformations 
March 2005 updated 13042012 