Fatti:
A. Il 29 novembre 2006 A._, sedicente cittadino marocchino privo di documenti di legittimazione, è stato condannato alla pena di 6 mesi di detenzione. Dopo aver chiesto vanamente inizio dicembre 2006 all'Ambasciata del Regno del Marocco un lasciapassare per l'interessato, l'Ufficio federale della migrazione ha pronunciato nei suoi confronti un divieto d'entrata in Svizzera fino al 14 febbraio 2017; la decisione è cresciuta in giudicato incontestata. Malgrado l'emanazione del citato provvedimento, A._ è però entrato più volte illegalmente nel nostro Paese ove ha continuato a delinquere, venendo altresì condannato a più riprese (decreti d'accusa del 1° marzo 2007, 11 ottobre 2007, 8 aprile 2008 e 28 maggio 2008).
B. Il 29 luglio 2008 la Sezione dei permessi e dell'immigrazione del Dipartimento delle istituzioni del Cantone Ticino ha disposto la carcerazione in vista di rinvio coatto di A._ per la durata di tre mesi in base all'art. 76 cpv. 1 lett. b numeri 3 e 4 LStr (RS 142.20), subordinatamente per la durata di un mese in applicazione dell'art. 78 LStr. La misura, attuata il giorno dopo, è stata confermata dal Giudice delle misure coercitive con giudizio del 31 luglio 2008. Ritenendo giustificato il provvedimento giusta l'art. 76 cpv. 1 lett. b numeri 3 e 4 LStr, questo non ha esaminato la fattispecie dal profilo dell'art. 78 LStr.
Il 12 agosto, 10 settembre e 15 ottobre 2008 la Sezione dei permessi e dell'immigrazione ha sollecitato l'Ufficio federale della migrazione per sapere se nel frattempo A._ fosse stato identificato oppure se fosse stato rilasciato un documento di viaggio per il suo rimpatrio. Un interrogatorio dello stesso previsto per il 15 ottobre 2008 non ha avuto luogo, dato che si è rifiutato di presenziare.
C. Il 17 ottobre 2008 la Sezione dei permessi e dell'immigrazione ha deciso di prorogare di ulteriori sei mesi la carcerazione di A._. Il 21 ottobre 2008 l'interessato si è determinato in proposito e il 22 ottobre 2008 è stato sentito in procedura orale dal Giudice delle misure coercitive il quale - lo stesso giorno - ha confermato la proroga della carcerazione.
D. Il 18 novembre 2008 A._ ha presentato dinanzi al Tribunale federale un ricorso in materia di diritto pubblico con cui chiede che la decisione del 22 ottobre 2008 sia annullata. Adduce, in sintesi, la violazione del principio della proporzionalità e del suo diritto di essere sentito.
Chiamati ad esprimersi la Sezione dei permessi e dell'immigrazione ha postulato la reiezione del gravame, mentre il Giudice delle misure coercitive si è riconfermato nelle motivazioni e conclusioni della decisione impugnata. L'Ufficio federale della migrazione ha rinunciato a presentare osservazioni.

Diritto:
1. Il presente gravame, rivolto contro una decisione di ultima istanza cantonale concernente una causa di diritto pubblico che non ricade sotto alcuna delle eccezioni di cui all'<ref-law>, è in linea di principio ricevibile quale ricorso in materia di diritto pubblico ai sensi dell'art. 82 segg. LTF (cfr. art. 82 lett. a e 86 cpv. 1 lett. d LTF). Risulta inoltre tempestivo (<ref-law>) ed è stato presentato da una persona legittimata ad agire (<ref-law>).
2. Il ricorrente sostiene che una proroga di sei mesi della carcerazione, decisa unicamente al fine di permettere all'autorità di espletare pratiche burocratiche, viola in modo troppo incisivo la propria libertà ed è quindi lesiva del principio della proporzionalità. A suo avviso una proroga di tre mesi, eventualmente rinnovabile, sarebbe stata sufficiente. Rimprovera poi all'autorità inferiore di avere disatteso il suo diritto di ottenere un giudizio motivato, in quanto si è limitata ad affermare che il provvedimento litigioso ossequiava il principio della proporzionalità senza però spiegare perché era stata decisa direttamente una proroga di sei mesi e non per un periodo più breve.
3. Il diritto di essere sentito di cui all'<ref-law> comprende l'obbligo per l'autorità di motivare le proprie decisioni. Tale obbligo ha lo scopo, da un lato, di porre la persona interessata nelle condizioni di afferrare le ragioni poste a fondamento della decisione, di rendersi conto della portata del provvedimento e di poterlo impugnare con cognizione di causa, e, dall'altro, di permettere all'autorità di ricorso di esaminare la fondatezza della decisione medesima. Ciò non significa tuttavia che l'autorità sia tenuta a pronunciarsi in modo esplicito ed esaustivo su tutte le argomentazioni addotte; essa può occuparsi delle sole circostanze rilevanti per il giudizio, atte ad influire sulla decisione (<ref-ruling> consid. 4.3; <ref-ruling> consid. 3.2; <ref-ruling> consid. 2b). Nel caso concreto l'autorità inferiore, riprodotti i testi legali applicabili ed esposto sia quanto addebitato al ricorrente sia quanto intrapreso dalle autorità e dopo avere valutato tutti gli elementi del caso, è giunta alla conclusione che il provvedimento litigioso risultava legale e adeguato. Nel gravame il ricorrente non sostiene di non essersi potuto rendere conto della portata del giudizio impugnato: già per questo motivo, la censura desunta dall'asserita carenza di motivazione del giudizio impugnato va respinta.
4. 4.1 Ai sensi dell'art. 76 cpv. 3 seconda frase LStr, se particolari ostacoli si oppongono all'esecuzione dell'allontanamento o dell'espulsione, la carcerazione secondo il capoverso 1 lettere a e b numeri 1 a 4 può essere prorogata, con il consenso dell'autorità giudiziaria cantonale, di 15 mesi al massimo o, se si tratta di minori tra i 15 e i 18 anni, di 9 mesi al massimo. I passi necessari per l'esecuzione dell'allontanamento o dell'espulsione devono essere intrapresi senza indugio (art. 76 cpv. 4 LStr). Conformemente alla giurisprudenza (cfr. <ref-ruling> consid. 3a, 377 consid. 2a) è necessario che l'esecuzione del rinvio sia momentaneamente impossibile (ad esempio in mancanza di documenti di legittimazione) ma comunque prevedibile entro un termine ragionevole (cfr. Andreas Zünd in: Spescha/Thür/Zünd/Bolzli, Kommentar Migrationsrecht, 2008, n. 1 all'art. 76). Inoltre l'ordine di carcerazione e l'esame della stessa devono adempiere le esigenze (segnatamente formali) imposte dall'art. 80 LStr.
4.2 Come emerge dalla decisione impugnata il ricorrente, sedicente marocchino privo di documenti d'identità e di mezzi di sostentamento, è arrivato in Svizzera, ove non ha alcuna relazione stabile, al più tardi nel 2006 venendovi condannato lo stesso anno ad una pena di 6 mesi di detenzione. In seguito, malgrado fosse colpito da un divieto d'entrata valido fino nel 2017, egli è tornato più volte illegalmente nel nostro Paese dove ha continuato a delinquere, venendo più volte condannato. Sentito una prima volta il 31 luglio 2008 dal Giudice delle misure coercitive, egli ha affermato di aver mentito riguardo alle sue vere generalità. Ha asserito di essere algerino, ma di aver perso il suo passaporto, e di essere ora disposto a collaborare. Sennonché, come constatato dall'autorità inferiore, egli è invece rimasto inattivo, non ha intrapreso alcunché per procurarsi i documenti necessari alla sua partenza, ha rifiutato di presenziare ad un interrogatorio indetto per il 15 ottobre 2008 ed, infine, ha espressamente dichiarato, nel corso della seconda audizione svoltasi il 22 ottobre 2008, che si opponeva ad un rimpatrio forzato. Alla luce di tutti questi elementi è quindi a giusto titolo che l'autorità precedente ha considerato - sia quando ha confermato la carcerazione che quando ha avallato la proroga della medesima - che erano (tuttora) soddisfatti i requisiti posti dall'art. 76 cpv. 1 lett. b numeri 3 e 4 LStr.
Anche le altre esigenze legali sono soddisfatte, segnatamente il provvedimento risulta rispettoso del principio della proporzionalità. Ricordato che la carcerazione può essere prolungata di 15 mesi al massimo (art. 76 cpv. 3 e 79 LStr), il fatto che nel caso concreto sia stata pronunciata direttamente una proroga di sei mesi, invece dei primi tre mesi usuali, costituisce il limite superiore ammissibile (cfr. <ref-ruling> consid. 4) senza essere però, viste le circostanze concrete, criticabile. In effetti si sa, per esperienza, che il trattamento delle richieste presentate alle rappresentanze diplomatiche dell'Algeria o del Marocco richiede tempo, ciò tanto più se, come nella fattispecie, il ricorrente ha fornito diverse identità e/o nomi e che non ha presentato veri documenti atti a provare le sue generalità. Va poi aggiunto - come peraltro già ricordato nella decisione querelata - che questi può ridurre la durata della sua carcerazione collaborando all'ottenimento di documenti di legittimazione. Al riguardo occorre precisare che solo in presenza di validi documenti potrà eventualmente essere valutata la richiesta formulata in sede cantonale di essere rinviato verso uno Stato terzo (art. 69 cpv. 2 LStr). Nel caso contrario solo il rimpatrio nel paese d'origine è invece possibile (<ref-ruling> consid. 4.2.2).
Per i motivi illustrati il ricorso si rivela infondato e deve pertanto essere respinto.
5. Visto l'esito del gravame le spese dovrebbero seguire la soccombenza ed essere poste a carico del ricorrente, il quale non ha peraltro formulato domanda di assistenza giudiziaria. Sennonché in casi di questa indole si giustifica di rinunciare a prelevare spese (<ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso è respinto.
2. Non si prelevano spese giudiziarie.
3. Comunicazione al patrocinatore del ricorrente, alla Sezione dei permessi e dell'immigrazione del Dipartimento delle istituzioni e al Giudice delle misure coercitive del Cantone Ticino nonché all'Ufficio federale della migrazione.