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.
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.
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.