Fatti: A. A._, cittadino italiano, ha ottenuto, il 28 novembre 2003, un permesso per confinanti per lavorare come agente di sicurezza nel Cantone Ticino. Il 9 giugno 2004 è stato posto al beneficio di un permesso di dimora CE/AELS, sempre per svolgere la stessa attività, valido fino all'8 giugno 2009. Nel settembre 2004 è stato licenziato. Dopo un periodo di disoccupazione, egli ha lavorato come cassiere ausiliario in un magazzino di Grancia dal 24 ottobre 2007 al 23 gennaio 2008 e dal 1° dicembre 2008 è stato assunto quale autista di autobus e aiuto operaio presso un'impresa luganese. B. Incarcerato a titolo preventivo dal 17 ottobre 2006 al 13 marzo 2007 A._ è stato condannato il 27 agosto 2008 dal Presidente della Corte delle Assise correzionali di Lugano a 24 mesi di detenzione, sospesi condizionalmente per un periodo di prova di 3 anni, per rapina. In seguito alla condanna la Sezione dei permessi e dell'immigrazione del Dipartimento delle istituzioni gli ha revocato, il 14 novembre 2008, il permesso di dimora CE/AELS per motivi di ordine pubblico nonché fissato un termine con scadenza al 13 dicembre 2008 per lasciare la Svizzera. La decisione è stato confermata su ricorso dapprima dal Consiglio di Stato, il 3 marzo 2009, e poi dal Tribunale cantonale amministrativo, con sentenza dal 19 maggio 2009. Rievocati i motivi della condanna, la Corte cantonale ha giudicato che la revoca dell'autorizzazione di soggiorno era giustificata sia dal profilo della legge federale sugli stranieri del 16 dicembre 2005 (LStr; RS 142.20) che da quello dell'Accordo del 21 giugno 1999 tra la Comunità europea e i suoi Stati membri, da una parte, e la Confederazione Svizzera, dall'altra, sulla libera circolazione delle persone (in seguito: ALC o Accordo sulla libera circolazione; RS 0.142.112.681). Il provvedimento risultava altresì rispettoso del principio della proporzionalità. C. Il 16 giugno 2009 A._ ha presentato dinanzi al Tribunale federale un ricorso con cui chiede che venga annullata la sentenza cantonale e che gli sia restituito il permesso dimora. In sintesi, censura la violazione dell'Accordo sulla libera circolazione e ritiene la revoca sproporzionata. Chiamati ad esprimersi, il Tribunale cantonale amministrativo si riconferma nelle motivazioni e nelle conclusioni della propria decisione, il Consiglio di Stato si rimette al giudizio del Tribunale federale, mentre la Sezione dei permessi e dell'immigrazione e l'Ufficio federale della migrazione propongono di respingere il gravame. D. Con decreto presidenziale del 14 luglio 2009 è stata accolta l'istanza di conferimento dell'effetto sospensivo contenuta nel ricorso. 