You are right on your thoughts about a solid being a better conductor than a gas. Metals are better conductors that nonmetals, since they have free electrons which can move thoughout the substance. A metal structure is made up of positive ions fixed into place, with a "sea" of free electrons. If one end of a metal rod gets heated, then the ions at that end vibrate faster, and so an electron colliding with it gains kinetic energy, then moves to the colder end, and collides with an ion there, passing on the kinetic energy.
In non-metals, there are no free electrons, and the only way in which heat is passed down the material is by the ions vibrating, and pssing these vibrations onto their nearest neighbour.