Sachverhalt:
A. Das Kreisgericht Rheintal sprach X._ von der Anklage der Veruntreuung frei. Die Zivilforderung des Privatklägers P._ im Betrag von Fr. 107'500.-- verwies es auf den Zivilweg.
Gegen diesen Entscheid erhob die Staatsanwaltschaft des Kantons St. Gallen Berufung. Eine vom Privatkläger eingereichte Anschlussberufung zog dieser später zurück. Das Kantonsgericht St. Gallen erklärte X._ mit Urteil vom 30. Juni 2009 der Veruntreuung schuldig und verurteilte ihn zu einer Freiheitsstrafe von neun Monaten. Auf den Widerruf einer einschlägigen bedingten Gefängnisstrafe des Bezirksgerichts Unterrheintal vom 28. März 2003 verzichtete das Kantonsgericht. Die Zivilforderung des Privatklägers verwies es auf den Zivilweg.
B. X._ führt Beschwerde in Strafsachen vor Bundesgericht, in der er beantragt, das angefochtene Urteil sei aufzuheben, und er sei von Schuld und Strafe freizusprechen. Eventualiter sei anstelle einer Freiheitsstrafe eine Geldstrafe von 180 Tagessätzen à Fr. 90.-- auszufällen. Subeventuell sei die Freiheitsstrafe auf sechs Monate zu reduzieren.
C. Die Staatsanwaltschaft des Kantons St. Gallen beantragt die kostenfällige Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Vorinstanz verzichtet auf eine Vernehmlassung.

Erwägungen:
1. Die Vorinstanz geht von folgendem Sachverhalt aus:
P._ vertraute Q._ drei ihm gehörende Sportwagen zum Verkauf an. Dieser gab den Auftrag dem Beschwerdeführer weiter, was P._ akzeptierte. Der Beschwerdeführer verkaufte die drei Sportwagen in der Zeit vom 28. Mai bis 24. August 2003 zu einem Gesamtpreis von Fr. 107'500.--. Später wurde der Vertrag insofern geändert, als der Beschwerdeführer beauftragt wurde, mit dem Verkaufserlös einen Ferrari 512 BB zu beschaffen. Nicht erstellt ist, ob dieses Fahrzeug aus dem Verkaufserlös tatsächlich erworben wurde. Unbestritten ist hingegen, dass der Beschwerdeführer bis heute weder den Erlös aus dem Verkauf der drei Sportwagen noch ein Eintausch-/ Ersatzfahrzeug herausgegeben oder sonst irgendeine Zahlung an P._ geleistet hat.
2. 2.1 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Die Feststellung des Sachverhalts durch die Vorinstanz kann nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich im Sinne von <ref-law> ist (<ref-ruling> E. 1.2.2), oder wenn sie auf einer Verletzung von schweizerischem Recht im Sinne von <ref-law> beruht (<ref-law>). Die Rüge der offensichtlich unrichtigen Feststellung des Sachverhalts prüft das Bundesgericht gemäss <ref-law> nur insoweit, als in der Beschwerde explizit vorgebracht und substantiiert dargelegt wird, inwiefern der Entscheid an einem qualifizierten und offensichtlichen Mangel leidet (<ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3 mit Hinweisen).
2.2 Der Beschwerdeführer rügt "Rechtsverletzungen durch die Vorinstanz" und legt im Folgenden dar, inwiefern es erwiesen sei, dass er einen Ferrari 512 BB gekauft und P._ angeboten habe. Was er gegen die tatsächlichen Feststellungen der Vorinstanz einwendet, erschöpft sich jedoch in einer blossen appellatorischen Kritik am angefochtenen Urteil, die für die Begründung einer willkürlichen Feststellung des Sachverhalts nicht genügt. Er beschränkt sich darauf, die eigene Sichtweise der Verhältnisse darzulegen und wiederholt darauf hinzuweisen, dass der Ferrari 512 BB P._ vertragsgemäss zur Verfügung gestanden habe. Einen Beleg hierfür bleibt der Beschwerdeführer schuldig (Beschwerde, S. 3 ff.).
2.3 Die Ausführungen des Beschwerdeführers sind insgesamt nicht geeignet, offensichtlich erhebliche und schlechterdings nicht zu unterdrückende Zweifel daran darzutun, dass sich der Sachverhalt, wie von der Vorinstanz dargestellt, verwirklicht hat. Denn für die Begründung von Willkür genügt praxisgemäss nicht, dass das angefochtene Urteil mit der Darstellung des Beschwerdeführers nicht übereinstimmt oder eine andere Lösung oder Würdigung vertretbar erscheint oder gar vorzuziehen wäre (<ref-ruling> E. 2b mit Hinweisen). Willkür im Sinne von <ref-law> liegt nach ständiger Rechtsprechung nur vor, wenn der angefochtene Entscheid auf einer schlechterdings unhaltbaren oder widersprüchlichen Beweiswürdigung beruht, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 1.3 S. 4 und 5; <ref-ruling> E. 5.4). Dies ist vorliegend nicht der Fall.
3. 3.1 Der Beschwerdeführer wendet sich gegen die Ausfällung einer Freiheitsstrafe (statt einer Geldstrafe) und gegen das Strafmass der Vorinstanz. Die Prüfung des Verschuldens sei einseitig und unvollständig ausgefallen. Die Vorinstanz habe bei der Strafzumessung die Tatsache unberücksichtigt gelassen, dass er alleinerziehender Vater eines Sohnes sei, der zurzeit die Lehre besuche. Ebenso sei das Verhalten von P._ völlig ausser Acht geblieben. Die Ausfällung einer Geldstrafe sei daher nicht nur möglich, sondern auch angezeigt. Der Beschwerdeführer beantragt die Ausfällung einer Geldstrafe von 180 Tagessätzen à Fr. 90.-- (in der Begründung geht er allerdings von Fr. 60.-- aus). Bei Bejahung einer Freiheitsstrafe durch das Bundesgericht sei diese von neun auf sechs Monate zu reduzieren (Beschwerde, S. 6).
3.2 Die Vorinstanz erwägt, das Verschulden des Beschwerdeführers wiege schwer, sei er doch einschlägig vorbestraft und habe nicht einmal ein Jahr nach seiner Verurteilung wieder delinquiert. Zudem sei der Deliktsbetrag hoch, und er weigere sich nach wie vor, über die für P._ getätigten Verkäufe und Käufe abzurechnen und die resultierenden Ausstände zu begleichen. Angesichts des Verschuldens komme daher einzig eine Freiheitsstrafe in Betracht, wenngleich theoretisch auch eine Geldstrafe möglich sei. Leicht strafmindernd könne berücksichtigt werden, dass seit der neuerlichen Tat rund fünfeinhalb Jahre vergangen seien (angefochtenes Urteil, S. 10).
3.3 Mit <ref-law> hat der Gesetzgeber für Strafen unter sechs Monaten eine gesetzliche Prioritätsordnung zugunsten nicht freiheitsentziehender Sanktionen eingeführt. Für Strafen von sechs Monaten bis zu einem Jahr sieht das Gesetz Freiheitsstrafe oder Geldstrafe vor (vgl. Art. 34 Abs. 1 und Art. 40 Satz 1 StGB). Im Vordergrund steht dabei ebenfalls die Geldstrafe. Das ergibt sich aus dem Prinzip der Verhältnismässigkeit, wonach bei alternativ zur Verfügung stehenden Sanktionen im Regelfall diejenige gewählt werden soll, die weniger stark in die persönliche Freiheit des Betroffenen eingreift bzw. die ihn am wenigsten hart trifft. Bei der Wahl der Sanktionsart sind als wichtige Kriterien die Zweckmässigkeit einer bestimmten Sanktion, ihre Auswirkungen auf den Täter und sein soziales Umfeld sowie ihre präventive Effizienz zu berücksichtigen (<ref-ruling> E. 4.2.2; <ref-ruling> E. 4.1; je mit Hinweisen).
3.4 Der Vorinstanz steht in der Wahl der Sanktionsart ein Ermessen zu. Mit Blick auf die bundesgerichtliche Rechtsprechung hat sie konkret zu prüfen und auch zu begründen, weshalb im Einzelfall eine Geldstrafe unzweckmässig und stattdessen eine Freiheitsstrafe auszusprechen ist. Die Begründungspflicht reicht nicht soweit, wie dies <ref-law> hinsichtlich der Ausfällung kurzer Freiheitsstrafen unter sechs Monaten verlangt. Allerdings sollten die Beweggründe des Gerichts für die eine oder andere Sanktionsform aus dem Urteil ersichtlich sein.
3.5 Die Vorinstanz führt aus, angesichts des Verschuldens des Beschwerdeführers falle einzig eine Freiheitsstrafe in Betracht. Das Verschulden vermag allerdings für sich alleine nicht die Ausfällung einer Freiheitsstrafe zu begründen, da dieses bei einer Sanktion bis zu einem Jahr auch mittels Geldstrafe abgegolten werden könnte. Auch die übrigen von der Vorinstanz angeführten Umstände, dass sich der Beschwerdeführer bis heute weigerte, über die für P._ getätigten Verkäufe und Käufe abzurechnen und die finanziellen Ausstände zu begleichen sowie der hohe Deliktsbetrag und die erneute Delinquenz zu Beginn der laufenden Probezeit stellen keine Begründungselemente dar, die anstelle einer Geldstrafe eine Freiheitsstrafe gebieten. Vielmehr beeinflussen diese Punkte das Strafmass. Die fehlende Begründung fällt umso mehr ins Gewicht, als erstinstanzlich ein Freispruch erfolgte und daher keine Begründung zur Ausfällung einer Freiheitsstrafe erforderlich war.
3.6 Der Beschwerdeführer macht im Weiteren sinngemäss eine erhöhte Strafempfindlichkeit als alleinerziehender Vater eines siebzehnjährigen Sohnes geltend (Beschwerde, S. 6). Obwohl bereits an der vorinstanzlichen Hauptverhandlung vorgebracht, ging die Vorinstanz im Rahmen der Strafzumessung auf diesen Umstand nicht ein. Sie wird sich daher zu diesem Punkt sowie zur Strafhöhe, die sie äusserst knapp begründete, noch äussern müssen.
4. Die Vorinstanz hat die ihr obliegende Begründungspflicht und damit Bundesrecht verletzt. Die Beschwerde ist deshalb gutzuheissen, soweit darauf einzutreten ist, und das angefochtene Urteil aufzuheben. Bei diesem Ausgang des Verfahrens sind keine Gerichtskosten zu erheben (Art. 66 Abs. 1 i.V.m. Abs. 4 BGG), und hat der Kanton St. Gallen dem Beschwerdeführer eine angemessene Parteientschädigung auszurichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, soweit darauf einzutreten ist. Das Urteil des Kantonsgerichts des Kantons St. Gallen vom 30. Juni 2009 wird aufgehoben und die Sache zur neuen Entscheidung an die Vorinstanz zurückgewiesen.
2. Es werden keine Gerichtskosten erhoben.
3. Der Kanton St. Gallen hat dem Beschwerdeführer eine Parteientschädigung von Fr. 3000.-- auszurichten.
4. Dieses Urteil wird den Parteien und dem Kantonsgericht St. Gallen, Strafkammer, schriftlich mitgeteilt.
Lausanne, 16. Februar 2010
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Favre Keller