Do Shochtim need any kind of certification or license in order to shecht? How does one get a license? What if someone slaughtered without one?
Midina d'Gemara, shochtim do not need to be certified. In halacha, we may assume like 'rov,' and in shechita, the rule is that 'rov metzuyim etzel shechita,' that most people who claim to know how to slaughter indeed know how to and may be relied upon.
See Simlah Chadasha 1:4-5.
However, in the times of the Rishonim, there were many fraudsters who took advantage of 'rov metzuyim,' and therefore the Maharam Mirutenberg decreed that no one may shecht without first receiving permission to do so from a rabbi. This way, no one has the chutzpa to claim having permission, and we can rely on them.
From this we derive the ktav kabbala -- literally script of acceptance (of permission), or "license to kill". After granting permission, the rabbi will write a license, basically vouching for the reliability of the shochet. See Simla Chadasha 1:5.
Now that ktav kabbala exists, one may not rely on rov metzuyin anymore, unless the shochet knows all the halachos EXCEPT for that of ktav kabbla (so that he is not rebelling against this rule) [sorry guys! ;)]
To get this license, one must know all of Hilchos Shechita (in America, as defined by the Simlah Chadasha [see this answer]), be tested on it by a rabbi (and know all of the common halachos, and some of the uncommon ones), and then kill three animals in front of the rabbi (in a row), to create a chazaka that he can actually shecht. See Simlah Chadashah 1:6.
Most test-givers will break the test-taker's knife, creating a pegimah (nick that invalidates the knife for use), and make the neophyte shochet fix it twice; so that we may establish (via chazaka [the first time he made his knife is before taking the test]) that he knows how to fix his knife.