Fatti: A. Il 17 febbraio 2000 la società C._SA, in qualità di locatrice, e A.A._ e B.A._, in qualità di conduttori, hanno sottoscritto un contratto di locazione avente per oggetto un appartamento di quattro locali al primo piano d'uno stabile di Viganello. Il canone di locazione mensile è stato fissato in fr. 1'440.--, oltre a un acconto a titolo di spese accessorie di fr. 125.-- "con conguaglio al termine del relativo esercizio". Il 2 dicembre 2001 la locatrice ha allestito il conteggio per le spese accessorie concernenti il periodo dal 1° giugno 2000 al 31 maggio 2001, con un saldo a proprio favore di fr. 1'935.05. I conduttori ne hanno criticato l'ammontare, anche dopo aver preso conoscenza della rettifica in fr. 1'619.65; in particolare hanno rimproverato alla locatrice di non averli informati dell'entità smisurata delle spese accessorie al momento della stipulazione del contratto. Per il periodo seguente, dal 1° giugno 2001 al 31 maggio 2002, la locatrice ha presentato un conteggio con un saldo a suo favore di fr. 1'767.40. B. I conduttori hanno adito il competente ufficio di conciliazione e poi la Pretura del Distretto di Lugano con istanza 23 luglio 2003, chiedendo di "invalidare la clausola contrattuale secondo cui parte conduttrice deve pagare un conguaglio eccedente gli acconti per spese accessorie al termine di ogni periodo di conteggio", così come di "annullare tutti i conguagli" e "accertare che l'importo di fr. 125.-- corrisposto da parte conduttrice è da considerarsi a forfait e non più quale acconto". Statuendo il 28 maggio 2008, la Pretore ha parzialmente accolto l'istanza. Ha annullato la clausola contrattuale impugnata, ridotto i due conguagli a fr. 300.-- ciascuno, e ordinato alle parti di "nuovamente pattuire la clausola di cui al punto 5 del contratto di locazione, ritenuto che in caso di mancato accordo gli inquilini saranno legittimati a disdire anzitempo il contratto". Adita dalla locatrice, con sentenza del 22 aprile 2009, la II Camera civile del Tribunale d'appello ha rovesciato la pronunzia di primo grado e interamente respinto l'istanza dei conduttori. C. Prevalendosi della violazione delle regole vigenti in caso di vizio del contratto, segnatamente di dolo, A.A._ e B.A._ sono insorti dinanzi al Tribunale federale con un ricorso in materia civile teso all'annullamento della sentenza del Tribunale d'appello e alla riconferma di quella del Pretore. Nelle osservazioni la locatrice propone di respingere il ricorso nella misura in cui risultasse ricevibile. L'autorità cantonale non si è invece determinata. 