Sachverhalt:
A. Der 1986 geborene X._, Staatsangehöriger von Gambia, reiste am 16. Mai 2004 in die Schweiz ein und stellte unter falschem Namen ein Asylgesuch. Nach dessen Abweisung verblieb er zunächst in der Schweiz und galt seit August 2007 als untergetaucht. Nachdem er in Gambia eine Schweizer Bürgerin geheiratet hatte, reiste er am 28. Januar 2008 im Rahmen des Familiennachzugs wieder in die Schweiz ein, wo ihm eine Aufenthaltsbewilligung erteilt und letztmals bis zum 27. Januar 2011 verlängert wurde.
Das Verhalten von X._ in der Schweiz gab Anlass zu schweren Klagen: Mit Urteil vom 21. Oktober 2010 verurteilte ihn das Kreisgericht X Thun wegen mehrfachen und teilweise qualifiziert begangenen Widerhandlungen gegen das Betäubungsmittelgesetz zu einer Freiheitsstrafe von 20 Monaten. Der Vollzug der Strafe wurde bei einer Probezeit von drei Jahren aufgeschoben. Als Folge dieser Delinquenz verweigerte die Einwohnergemeinde Bern mit Verfügung vom 28. April 2011 die Verlängerung der Aufenthaltsbewilligung von X._.
B. Gegen die Nichtverlängerung seiner Aufenthaltsbewilligung beschwerte sich X._ ohne Erfolg bei der Polizei- und Militärdirektion des Kantons Bern: Diese wies die Beschwerde mit Entscheid vom 26. Juli 2011 ab. Hiergegen führte X._ Beschwerde beim Verwaltungsgericht des Kantons Bern, welches das Rechtsmittel mit Urteil vom 2. Februar 2012 abwies.
C. Mit Eingabe vom 7. März 2012 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er stellt den Antrag, es sei das Urteil des Verwaltungsgerichts aufzuheben und ihm die Aufenthaltsbewilligung zu verlängern.
Die Einwohnergemeinde der Stadt Bern, die Polizei- und Militärdirektion sowie das Verwaltungsgericht des Kantons Bern und das Bundesamt für Migration beantragen die Abweisung der Beschwerde.
Mit Verfügung vom 12. März 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist unzulässig gegen Entscheide auf dem Gebiet des Ausländerrechts betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen (<ref-law>).
Gemäss Art. 42 Abs. 1 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) haben ausländische Ehegatten und ledige Kinder unter 18 Jahren von Schweizerinnen und Schweizern Anspruch auf Erteilung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen. Ein analoger Anspruch besteht zudem aufgrund des in Art. 8 EMRK bzw. <ref-law> garantierten Rechts auf Achtung des Familienlebens (vgl. E. 3.2 hiernach). Der Beschwerdeführer ist mit einer Schweizer Bürgerin verheiratet und wohnt mit ihr zusammen. Er hat damit einen grundsätzlichen Anspruch auf Erteilung der Aufenthaltsbewilligung. Ob der Anspruch erloschen ist, weil - wie die Vorinstanzen angenommen haben - ein Widerrufsgrund nach Art. 63 Abs. 1 lit. a i.V.m. Art. 62 lit. b und Art. 51 Abs. 1 lit. b AuG vorliegt, ist eine Frage der materiellen Beurteilung und nicht der Zulässigkeit des Rechtsmittels (<ref-ruling> E. 1.1.5 S. 149 f.).
Nach dem Ausgeführten steht im vorliegenden Fall die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen, und es kann auf das im Übrigen form- und fristgerecht eingereichte Rechtsmittel eingetreten werden.
2. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law> bzw. <ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>; vgl. <ref-ruling> E. 1.5 S. 146 f.).
Der Beschwerdeführer bestreitet den vorinstanzlich festgestellten Sachverhalt grundsätzlich nicht. Er stellt jedoch in Abrede, dass seine Ehefrau seine Delinquenz gekannt und folglich damit habe rechnen müssen, die Ehe möglicherweise nicht in der Schweiz leben zu können. Im angefochtenen Entscheid (S. 12) stellte die Vorinstanz, insbesondere unter Verweis auf die Begründung des Strafurteils des Kreisgerichts X Thun vom 21. Oktober 2010 eingehend die Umstände dar, die darauf schliessen lassen, dass der Ehefrau das deliktische Verhalten ihres Gatten bereits im Zeitpunkt der Heirat bekannt gewesen sein musste. Der Beschwerdeführer zeigt nicht auf, weshalb diese sachverhaltlichen Feststellungen der Vorinstanz offensichtlich unrichtig sein oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen sollten. Nach dem hiervor Ausgeführten bleibt das Bundesgericht folglich daran gebunden.
3. 3.1 Gemäss Art. 51 Abs. 1 lit. b AuG erlöschen die Ansprüche nach Art. 42 AuG u.a. wenn Widerrufsgründe nach Art. 63 AuG vorliegen. Einen derartigen Widerrufsgrund setzt ein Ausländer insbesondere dann, wenn er "zu einer längerfristigen Freiheitsstrafe verurteilt wurde" (Art. 63 Abs. 1 lit. a AuG in Verbindung mit Art. 62 lit. b AuG). Als längerfristig im Sinne von Art. 62 lit. b AuG gilt eine Freiheitsstrafe, wenn ihre Dauer ein Jahr überschreitet (<ref-ruling> E. 4.2 und E. 4.5 S. 379 ff.).
Liegt ein Widerrufsgrund vor, so ist zu prüfen, ob diese Massnahme bzw. die Nichtverlängerung der Bewilligung auch als verhältnismässig erscheint, wobei namentlich die Schwere des Verschuldens, die Dauer der Anwesenheit sowie die dem Betroffenen und seiner Familie drohenden Nachteile zu berücksichtigen sind (vgl. Art. 96 AuG; <ref-ruling> E. 4.3 S. 381 mit Hinweisen). Was das Fernhalteinteresse anbetrifft, so darf bei Ausländern, welche sich - wie hier - nicht auf das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (Freizügigkeitsabkommen, FZA; SR 0.142.112.681) berufen können, im Rahmen der Interessenabwägung namentlich auch generalpräventiven Gesichtspunkten Rechnung getragen werden (Urteil 2C_1026/2011 vom 23. Juli 2012 E. 3 mit Hinweis).
In <ref-ruling> E. 4.4 S. 382 f. hat das Bundesgericht im Grundsatz auch die sog. "Reneja-Praxis" bestätigt, wonach dem Ausländer im Falle einer Verurteilung zu einer Freiheitsstrafe von zwei Jahren in der Regel selbst dann kein Aufenthaltstitel mehr zu erteilen ist, wenn der schweizerischen Ehepartnerin die Ausreise nicht oder nur schwer zuzumuten ist. Wie bis anhin stellt diese "Zweijahresregel" keinesfalls eine feste Grenze dar, die nicht über- oder unterschritten werden dürfte. Vielmehr erweist sich weiterhin die Abwägung der widerstreitenden öffentlichen und privaten Interessen im Einzelfall als entscheidend (<ref-ruling> E. 4b S. 14).
3.2 Hat ein Ausländer nahe Verwandte mit einem gefestigten Anwesenheitsrecht in der Schweiz und wird die intakte familiäre Beziehung tatsächlich gelebt, kann es Art. 8 Ziff. 1 EMRK bzw. <ref-law> verletzen, wenn ihm die Anwesenheit in der Schweiz untersagt und damit sein Familienleben vereitelt wird (<ref-ruling> E. 3.1 S. 285 mit Hinweisen). Der betreffende Anspruch gilt indessen nicht absolut. Vielmehr ist nach Art. 8 Ziff. 2 EMRK ein Eingriff in das durch Ziff. 1 geschützte Rechtsgut statthaft, soweit er gesetzlich vorgesehen ist und eine Massnahme darstellt, die in einer demokratischen Gesellschaft für die nationale Sicherheit, die öffentliche Ruhe und Ordnung, das wirtschaftliche Wohl des Landes, die Verteidigung der Ordnung und zur Verhinderung von strafbaren Handlungen, zum Schutz der Gesellschaft und Moral sowie der Rechte und Freiheiten anderer notwendig ist. Die Konvention verlangt insofern eine Abwägung der sich gegenüberstehenden privaten Interessen an der Bewilligungserteilung und den öffentlichen Interessen an deren Verweigerung, wobei Letztere in dem Sinne überwiegen müssen, dass sich der Eingriff als notwendig erweist (<ref-ruling> E. 2.1 S. 147; <ref-ruling> E. 2.2.1 S. 156; <ref-ruling> E. 2 S. 6 mit Hinweisen). Bei der Interessenabwägung im Rahmen von Art. 8 Ziff. 2 EMRK sind die Schwere des begangenen Delikts, der seit der Tat vergangene Zeitraum, das Verhalten des Ausländers während dieser Periode, die Auswirkungen auf die betroffene Person sowie deren familiäre Situation zu berücksichtigen. Zudem sind die Dauer der ehelichen Beziehung und weitere Gesichtspunkte relevant, welche Rückschlüsse auf deren Intensität zulassen (Geburt und Alter allfälliger Kinder; Kenntnis der Tatsache, dass die Beziehung wegen der Straftat unter Umständen nicht in der Schweiz gelebt werden kann). Von Bedeutung sind auch die Nachteile, welche dem Ehepartner oder den Kindern erwachsen würden, müssten sie dem Betroffenen in dessen Heimatstaat folgen (<ref-ruling> E. 4.3 in fine S. 381 f. mit Hinweisen; vgl. auch die Urteile des EGMR Nr. 46410/99 vom 18. Oktober 2006 i.S. Üner gegen die Niederlande Rz. 57, sowie Nr. 1638/03 vom 23. Juni 2008 i.S. Maslov gegen Österreich Rz. 68 ff.).
4. 4.1 Aufgrund der Verurteilung des Beschwerdeführers zu einer "längerfristigen" Freiheitsstrafe von 20 Monaten ist vorliegend ein Widerrufsgrund nach Art. 62 lit. b AuG i.V.m Art. 63 Abs. 1 lit. a AuG gegeben, was der Beschwerdeführer zu Recht nicht bestreitet. Umstritten und somit zu prüfen ist dagegen die Verhältnismässigkeit der angeordneten Massnahme.
4.2 Das Verwaltungsgericht hat - zum Teil unter Verweis auf den Beschluss des Regierungsrates und die ergangenen Strafurteile - im Wesentlichen erwogen, die Nichtverlängerung der Aufenthaltsbewilligung erwiese sich trotz bestehender Ehe mit einer Schweizer Bürgerin als verhältnismässig, denn der Beschwerdeführer sei längere Zeit im Drogenhandel tätig gewesen und bereits vor der strafrechtlichen Verurteilung u.a. durch Verhaltensweisen aufgefallen, welche zur Ausgrenzung aus der Gemeinde Bern, einem Stadtgebiet von Thun bzw. der gesamten Gemeinde Thun sowie aus dem Kanton Luzern geführt hätten. Von einer gelungenen Integration in der Schweiz könne jedenfalls nicht die Rede sein. Seiner Frau sei es zwar nicht zuzumuten, ihm nach Gambia zu folgen, und es sei nicht ausgeschlossen, dass sie die begonnene Ausbildung, welche ihr Gatte finanziell unterstütze, werde abbrechen müssen. Damit habe sie aber bereits rechnen müssen, als sie diese begonnen habe. Insgesamt erweise sich die Nichtverlängerung der Aufenthaltsbewilligung als verhältnismässig, zumal sich der Beschwerdeführer problemlos wieder in seinem Heimatland werde integrieren können.
4.3 Der Beschwerdeführer wendet hiergegen ein, er finanziere den ehelichen Lebensunterhalt und habe von seiner kriminellen Vergangenheit endgültig Abstand genommen, was sich darin äussere, dass er sich seit nunmehr bald drei Jahren wohl verhalte. Sodann sei er bloss zu einer bedingt vollziehbaren Strafe verurteilt worden, was nicht der Fall gewesen wäre, wenn er eine Gefahr für die Öffentlichkeit darstellen würde. Diese Aspekte seien vom Verwaltungsgericht nicht genügend berücksichtigt worden. Stattdessen habe die Vorinstanz die "Reneja-Praxis" schematisch und ohne ausführliche Ermessensabwägung angewendet: In Fällen wie dem vorliegenden, in denen dem schweizerischen Ehegatten die Ausreise ins Ausland nicht zuzumuten sei, werde die Aufenthaltsbewilligung in der Regel verlängert.
4.4 Den Einwendungen des Beschwerdeführers kann nicht gefolgt werden:
Die Vorinstanz hat entgegen dem Vorwurf des Beschwerdeführers nicht ohne Weiteres von der Höhe des Strafmasses auf die Anwendung der "Reneja-Praxis" bzw. auf eine Nichtverlängerung der Bewilligung geschlossen. Vielmehr hat sie in E. 4.1 des angefochtenen Entscheids die öffentlichen Interessen an der Nichtverlängerung der Aufenthaltsbewilligung aufgezeigt und diese in der darauf folgenden E. 4.2 den privaten Interessen des Beschwerdeführers am weiteren Verbleib in der Schweiz gegenüber gestellt. Die vorinstanzlichen Überlegungen erweisen sich als zutreffend, und was der Beschwerdeführer dagegen vorbringt, ändert an dieser Einschätzung nichts.
Sodann ist der Auffassung des Verwaltungsgerichts zuzustimmen, dass sich aus der Gewährung des bedingten Strafvollzugs nicht ohne Weiteres auf eine günstige Prognose schliessen lässt: Der bedingte Aufschub einer Freiheitsstrafe zwischen sechs Monaten und zwei Jahren ist seit Inkrafttreten des neuen Allgemeinen Teils des Strafgesetzbuches per 1. Januar 2007 der Regelfall und setzt nur noch das Fehlen einer explizit ungünstigen Prognose voraus (<ref-law>; <ref-ruling> E. 7.3 S. 117; Urteile 6B_122/2011 vom 17. Mai 2011 E. 3.1; 2C_160/2009 vom 1. Juli 2009 E. 3.4). Wenn der Beschwerdeführer ausführt, er habe von seiner Delinquenz "nachweislich" endgültig Abstand genommen und sich dabei auf das Ausbleiben von Verurteilungen in den vergangenen drei Jahren beruft, überzeugt dies ebenfalls nicht: Beizupflichten ist der Einschätzung des Verwaltungsgerichts, dass sich das Risiko eines Rückfalls angesichts seines bisherigen deliktischen Verhaltens in der Schweiz trotz bestehender Ehe und Arbeitsstelle nicht in Abrede stellen lässt; dies gilt umso mehr, als offenbleiben muss, ob das Ausbleiben von Straftaten nicht bloss auf das laufende Wegweisungsverfahren zurückzuführen ist. Wie die Vorinstanz überdies zu Recht ausführt, kann die Integration des Beschwerdeführers in der Schweiz nicht als besonders erfolgreich gelten: Er spricht die Landessprachen kaum und ist gerade erst dabei, sich auf dem hiesigen Arbeitsmarkt zu etablieren. Abgesehen von seiner Delinquenz hat auch sein ordnungsgemässer Aufenthalt in der Schweiz nicht lange gedauert. Schliesslich erscheint eine Rückkehr auch als zumutbar: Der Beschwerdeführer ist erst als Erwachsener in die Schweiz gekommen; er ist in Gambia aufgewachsen und es fehlen jegliche Hinweise, dass er sich in seinem Heimatland nicht problemlos wieder würde integrieren können.
Es trifft zu, dass der Beschwerdeführer familienrechtlich zur Unterstützung seiner Ehefrau verpflichtet ist. Diese hat vor knapp zwei Jahren eine Ausbildung begonnen und wird dabei von ihm finanziell unterstützt. Dies schliesst indes nicht aus, dass sie bei Wegfall dieser Hilfe allenfalls auf andere Leistungen zurückgreifen kann, seien es staatliche Darlehen bzw. Stipendien oder Unterstützungszahlungen seitens der Eltern, selbst wenn diese keine Unterhaltspflicht trifft. Massgebend im Zusammenhang mit den Interessen der Ehefrau ist zudem insbesondere auch, dass die Ehefrau angesichts der gesamten Umstände und aufgrund ihrer eigenen Erkenntnisse schon bei Eheschluss gewusst haben musste, dass sich der Beschwerdeführer im Drogenmilieu bewegte und ihm deswegen Fernhaltemassnahmen drohten (E. 3.2 hiervor; vgl. auch das Urteil des EGMR Nr. 54273/00 vom 2. August 2001 i.S. Boultif gegen die Schweiz Rz. 48). Sie durfte daher bereits zu Beginn ihrer Ausbildung nicht davon ausgehen, längerfristig auf die finanzielle Unterstützung ihres Gatten zählen zu können. Da in der Beschwerde weitere Ausführungen zu diesem Punkt fehlen, braucht darauf nicht weiter eingegangen zu werden.
Bei dieser Sachlage ist die Schlussfolgerung des Verwaltungsgerichts nicht zu beanstanden, dass die öffentlichen Interessen an der Nichtverlängerung der Aufenthaltsbewilligung des Beschwerdeführers dessen private Interessen an einem Verbleib in der Schweiz überwiegen.
5. Nach dem Ausgeführten ist die Beschwerde unbegründet und somit abzuweisen.
Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer an sich kostenpflichtig (<ref-law>). Da er bedürftig ist und seine Eingabe nicht als von vornherein aussichtslos zu bezeichnen ist, kann jedoch seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung entsprochen werden (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
a) Es werden keine Gerichtskosten erhoben.
b) Fürsprecher Peter D. Deutsch, Bern, wird als unentgeltlicher Rechtsbeistand des Beschwerdeführers bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2'000.-- ausgerichtet.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Bern sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 23. August 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Zähndler