The amount of heatsinking you need on a regulator depends on how much power it dissipates.
For a switching regulator, you can estimate this from the efficiency. Here is one way (not necessarily the best way) to calculate it. Say the regulator is 80% efficient and your maximum load on the regulator output will be 1A at 13.5V. That's 13.5W output, which is 80% of the input power, so the input power is 13.5 / 0.8 which is 16.9W. The regulator will waste 20% of this, i.e. 3.4W, as heat. This heat will come mainly from the switching device and the catch diode.
For a linear regulator, the power dissipated is equal to the voltage ACROSS the regulator (that is, the input voltage minus the output voltage) multiplied by the current. For example if the solar panel is generating 18V and the load on the regulator is 1A at 13.5V, the voltage across the regulator will be (18 - 13.5) = 4.5V. Multiply this by the current, 1A, and your dissipation in the regulator is 4.5 watts.
Heatsinking affects the ratio between power dissipated, and temperature rise above ambient. This factor is called thermal resistance, and is defined in degrees Celsius per watt. A lower thermal resistance corresponds to better heatsinking. See
http://en.wikipedia.org/wiki/Thermal_resistance. Thermal resistance to ambient depends mainly on surface area and airflow.
The thermal resistance to ambient of a typical three-terminal regulator in a TO-220 package in free air (not fan-cooled) is (very) roughly 100 degrees Celsius per watt. That means that for every watt dissipated, its temperature will rise by 100 degrees Celsius over ambient. If it's dissipating 4.5W its temperature will be 450 degrees Celsius above ambient! Or it would be, but the device will shut down around 150 degrees to prevent damage. So it would definitely need heatsinking.
Adding enough heatsinking to reduce the thermal resistance to, say, 15 degrees Celsius per watt will reduce the temperature to 67.5 degrees Celsius above ambient, or about 90 degrees Celsius at room temperature. This is still very high, and will reduce the lifespan of the regulator and cause a burn injury risk. A heatsink with a lower thermal resistance - 12 or 10 degrees per watt - would be a lot better. Or you can use a fan or some other forced cooling method to reduce the thermal resistance to ambient.
There are other factors to consider, such as the thermal resistance between the semiconductor junction and the case, and from the case to the heatsink, but since these paths are through solid materials, they are relatively small compared to the thermal resistance to ambient in free air.
Switching regulators may not need external heatsinking because the heat-dissipating components are often mounted directly onto the copper on the circuit board, which provides some heatsinking, because there are two sources of heat instead of just one, and because switching regulators are normally more efficient than linear regulators.
For circuit examples, do a Google image search on the relevant keywords. You should probably first decide whether you want a linear regulator or a switching regulator.
