Fatti: A. Dal 1982 A.A._ e B.A._ sono titolari di una relazione bancaria denominata xxx, prima presso la banca D._ e poi presso la banca C._, che ne ha ripreso l'attività; della relazione bancaria si è sempre occupato il medesimo funzionario. B. L'attuale controversia trae origine da un'operazione finanziaria avvenuta tra il marzo e il giugno 2000, avente per oggetto l'acquisto di titoli obbligazionari della Repubblica Argentina per un importo di Euro 600'000.--, il cui rimborso è poi stato sospeso a causa del default dello Stato argentino. B.a Rimproverando alla banca di non aver gestito il loro patrimonio con la necessaria diligenza, il 6 giugno 2006 A.A._ e B.A._ hanno convenuto la banca C._, succursale di Lugano, direttamente dinanzi al Tribunale d'appello del Cantone Ticino onde ottenere il risarcimento del danno subito in esito all'operazione sopra descritta, di complessivi fr. 733'692.90, da cui vanno dedotti Euro 73'095.--, pari agli interessi maturati e versati sulle citate obbligazioni. La banca ha negato ogni responsabilità siccome non incaricata della gestione del conto degli attori, i quali hanno personalmente deciso e ordinato l'acquisto delle obbligazioni argentine. B.b Con sentenza del 14 aprile 2008, intimata il 17 aprile seguente, la II Camera civile del Tribunale d'appello del Cantone Ticino ha integralmente respinto la petizione. In assenza di un formale mandato di gestione a favore della banca, i giudici cantonali hanno stabilito che toccava agli attori, gravati dall'onere probatorio, dimostrare che il loro conto veniva gestito autonomamente dalla banca e/o che l'acquisto delle obbligazioni argentine era avvenuto su iniziativa di questa. Non avendo essi fornito alcuna prova al riguardo, la Corte ticinese ha negato di poter imputare alla banca una responsabilità per il danno subito dai clienti. La stessa conclusione si imporrebbe - hanno aggiunto i giudici del Tribunale d'appello - anche applicando il principio giurisprudenziale che impone eccezionalmente l'obbligo della banca di informare il cliente se riconosce che questi non era consapevole del rischio insito in un determinato investimento o se tra loro è venuta in essere una particolare relazione di fiducia a causa del prolungato rapporto contrattuale, giacché gli attori non erano privi di conoscenze bancarie e la composizione del loro portafoglio indicava una certa propensione al rischio; inoltre, nel marzo 2000 l'operazione non appariva come manifestamente irragionevole. Nessun rimprovero può infine essere mosso alla banca per non aver informato gli attori del declassamento dei titoli nel marzo 2001, poiché un tale obbligo - insieme all'obbligo di intervenire per garantire il patrimonio del cliente - esiste solo in presenza di un mandato di gestione. C. Contro questa decisione A.A._ e B.A._ sono insorti, il 26 maggio 2008, dinanzi al Tribunale federale con un ricorso in materia civile tendente alla modifica della sentenza cantonale nel senso dell'accoglimento della petizione per l'importo di fr. 624'050.40, oltre interessi del 5 % dal 31 gennaio 2005. Con risposta del 7 luglio 2008 la banca C._, contestata l'ammissibilità del ricorso sotto il profilo della motivazione, ha proposto di respingerlo nel merito. L'autorità cantonale ha invece rinunciato a presentare osservazioni.