Fatti: A. Il cittadino nigeriano A._ si è sposato con la cittadina elvetica B._ il 20 aprile 2007, a Y._ (Spagna). Il 3 giugno 2007, dal loro matrimonio è nata la figlia C._, data in affidamento a terzi nell'agosto seguente. Privo del necessario visto, A._ è entrato illegalmente in Svizzera il 21 giugno 2008. Arrestato tre giorni più tardi, è rimasto in carcere fino al 15 settembre di quell'anno. Nel frattempo, il 10 luglio 2008, B._, già sotto curatela amministrativa a causa della sua dipendenza dall'alcool e da sostanze stupefacenti, è stata collocata presso una comunità per tossicodipendenti. Interrogato dalla Polizia cantonale, il 25 settembre 2008 A._ ha dichiarato di avere vissuto a X._ con la moglie dal luglio al dicembre 2006, di essersi trasferito a Y._ ed essere infine rientrato in Ticino ai primi di maggio 2007, per risiedere con la moglie presso la suocera. Egli ha tuttavia specificato di non aver più vissuto insieme alla moglie già dal giugno 2007, per motivi economici. B. Il 16 ottobre 2008, A._ ha inoltrato alla Sezione dei permessi e dell'immigrazione del Dipartimento delle istituzioni del Cantone Ticino un'istanza volta al rilascio di un permesso di dimora per ricongiungersi con la moglie in Svizzera. Detta domanda è stata respinta il 16 dicembre 2008 a causa delle condanne penali pronunciate a carico del richiedente in Svizzera e all'estero. Ad A._ è stato quindi assegnato un termine scadente il 31 gennaio 2009 per lasciare il territorio elvetico. Tale decisione è stata confermata su ricorso dal Consiglio di Stato il 1° aprile 2009 e, in seguito, dal Tribunale cantonale amministrativo, con sentenza del 17 agosto 2009. C. Il 22 settembre 2009, A._ ha inoltrato un ricorso al Tribunale federale. Con tale atto, oltre alla concessione dell'effetto sospensivo e dell'assistenza giudiziaria, chiede l'annullamento della sentenza cantonale e il rilascio del permesso di dimora o, in subordine, il rinvio degli atti all'autorità inferiore per un nuovo esame. Con decreto presidenziale del 25 settembre 2009, è stato concesso l'effetto sospensivo al gravame. Chiamato ad esprimersi, il Tribunale cantonale amministrativo si è riconfermato nelle motivazioni e nelle conclusioni della propria sentenza. Ad essa ha fatto rinvio anche la Sezione dei permessi e dell'immigrazione e l'Ufficio federale della migrazione. Il Consiglio di Stato si è invece rimesso al giudizio di questa Corte.