Fatti:
A. Il 24 luglio 2003 A._ e B._ hanno chiesto al Municipio di Cadro il permesso di costruire, sulla particella xxx sita fuori della zona edificabile, a confine con quella residenziale, una tettoia di 15 x 10 m da destinare al deposito di legname. Preso atto del preavviso negativo del Dipartimento del territorio, che riteneva non adempiuti i requisiti dell'ubicazione vincolata e dell'assenza di interessi preponderanti contrari, il Municipio ha respinto la domanda il 17 marzo 2004. Il 26 marzo successivo, il Municipio, senza interpellare l'autorità cantonale, ha nondimeno rilasciato agli istanti un'autorizzazione "provvisoria" della durata di un anno (rinnovabile) per realizzare l'opera. Il manufatto, così eretto, è formato da una struttura in carpenteria metallica sorretta da sei pilastri alti da 4 a 5 m, fissati su basamenti in cemento armato. Sotto la tettoia sono accatastati ingenti quantitativi di tronchi d'albero, che i proprietari tagliano con motoseghe.
B. Il 7 dicembre 2007 il Municipio, raccolto il necessario consenso del Dipartimento, ha ordinato lo smantellamento della tettoia, nel frattempo divenuta priva anche dell'autorizzazione provvisoria di cui gli istanti non avevano chiesto il rinnovo. Con decisione del 16 aprile 2008 il Consiglio di Stato del Cantone Ticino ha confermato l'ordine di demolizione. Il Tribunale cantonale amministrativo, statuendo il 25 settembre 2008, ha respinto un ricorso dei proprietari.
C. Avverso questo giudizio A._ e B._ presentano un ricorso di diritto pubblico al Tribunale federale. Chiedono di annullare la decisione impugnata e di rinviare gli atti di causa alla Corte cantonale, indicando di evitare la demolizione dell'opera e di sostituirla con una sanzione pecuniaria.
Non sono state chieste osservazioni al ricorso, ma è stato richiamato l'incarto cantonale.

Diritto:
1. 1.1 Il Tribunale federale esamina d'ufficio se e in che misura un ricorso può essere esaminato nel merito (<ref-ruling> consid. 2).
1.2 Presentato tempestivamente contro una decisione finale dell'ultima istanza cantonale, che ha confermato l'ordine, fondato sul diritto pubblico, di demolire una tettoia, il ricorso in materia di diritto pubblico (art. 82 lett. a, 86 cpv. 1 lett. d, 90 e 100 cpv. 1 LTF), e non più il ricorso di diritto pubblico giusta il previgente OG, è di massima ammissibile (<ref-ruling> consid. 1.1). La legittimazione dei ricorrenti è pacifica.
1.3 Conformemente a quanto stabilito dall'<ref-law>, il ricorso ordinario al Tribunale federale può essere presentato, tra l'altro, per violazione del diritto federale e dei diritti costituzionali (lett. a e c). Secondo l'art. 42 cpv. 1 e 2 LTF, il gravame dev'essere motivato in modo sufficiente, spiegando nei motivi perché l'atto impugnato viola il diritto (<ref-ruling> consid. 1.4.1; <ref-ruling> consid. 1.4). Il Tribunale federale esamina in linea di principio solo le censure sollevate; esso non è tenuto a vagliare, come lo farebbe un'autorità di prima istanza, tutte le questioni giuridiche che si pongono, se queste ultime non sono presentate nella sede federale (<ref-ruling> consid. 2.2; <ref-ruling>). Inoltre, quando, come in concreto, il ricorrente invoca la violazione di diritti fondamentali e di norme del diritto cantonale, giusta l'<ref-law> il Tribunale federale esamina le censure soltanto se sono state esplicitamente sollevate e motivate in modo chiaro e preciso, conformemente alla severa prassi, fondata sull'art. 90 cpv. 1 lett. b OG, applicabile nel quadro del previgente ricorso di diritto pubblico (<ref-ruling> consid. 2.1 e 2.2). Le esigenze di motivazione sono inoltre accresciute laddove il ricorrente lamenta l'arbitrio nell'accertamento dei fatti e nella valutazione delle prove, dato che ciò equivale a sostenere che i fatti sono stati accertati in violazione dell'<ref-law> e del diritto federale (DTF <ref-ruling> consid. 1.4.1). In questa misura, argomentazioni vaghe o meramente appellatorie e semplici rinvii agli atti cantonali non sono quindi ammissibili (<ref-ruling> consid. 2.1 e rinvii). Come si vedrà, l'atto di ricorso disattende in larga misura queste severe esigenze di motivazione ed è quindi, in gran parte, inammissibile.
2. 2.1 Il Tribunale cantonale amministrativo ha accertato che il Consiglio di Stato non ha accolto la richiesta dei ricorrenti di esperire un sopralluogo inteso a verificare l'accennata sussistenza di ulteriori abusi edilizi, non apparendo detto atto istruttorio necessario per valutare l'asserita sussistenza di una violazione dell'uguaglianza giuridica: ciò poiché non erano comunque date le condizioni per accogliere eccezionalmente la censura relativa alla parità di trattamento nell'illegalità. La Corte cantonale, condiviso questo apprezzamento anticipato delle prove, ha stabilito che l'accenno dei ricorrenti ad altre 4/5 situazioni analoghe non dimostrava del tutto la lesione del principio dell'uguaglianza giuridica. Essa ha poi aggiunto che, indipendentemente dall'eventuale esistenza di altri singoli casi di abuso, nulla permetteva di ravvisare una prassi contraria al diritto perseguita dalle autorità e ch'esse si rifiuterebbero d'abbandonare.
2.2 Al riguardo, i ricorrenti si limitano ad addurre, in maniera del tutto generica, che i casi citati nel ricorso al Tribunale amministrativo sarebbero tuttora tollerati sia dal Municipio sia dal Dipartimento del territorio. Aggiungono che nel quadro del richiesto sopralluogo, il cui mancato esperimento non è tuttavia più contestato nel ricorso in esame, per lo meno con una motivazione conforme a quanto imposto dagli art. 42 cpv. 2 e 106 cpv. 2 LTF, si sarebbero potute ravvisare le altre asserite "situazioni simili (deposito e taglio di legna) illegali". I ricorrenti non negano di per sé la facoltà del Governo cantonale di procedere nella fattispecie a un apprezzamento anticipato delle prove (su questo tema vedi <ref-ruling> consid. 3) e si limitano a rilevare che il loro "accenno a 4/5 situazioni analoghe vale appunto come formale avvertimento" affiché tutte le analoghe situazioni vengano trattate alla pari "e lascia eccome intendere una lesione del principio di uguaglianza giuridica". Questo semplice accenno non adempie chiaramente le citate esigenze di motivazione e non dimostra l'asserita disparità di trattamento. Per di più, le presunte situazioni illegali, addotte nel ricorso alla Corte cantonale, si riferiscono in gran parte a sostenuti tagli di legna abusivi, fattispecie che esula dall'oggetto del litigio.
La stessa conclusione vale per il riferimento, ininfluente ai fini del giudizio, che, con il suo voto negativo all'aggregazione con Lugano, la popolazione del Comune di Cadro avrebbe scelto l'autonomia, mantenendo determinate prerogative di un passato rurale e di attività manuali che andrebbero salvaguardate. In effetti, l'ordine di smantellamento litigioso, come l'impossibilità di autorizzare eccezionalmente la tettoia in esame, si fondano sulla legislazione federale (sentenza 1A.196/2003 del 10 febbraio 2004 consid. 4, in RtiD 2004-II n. 18 pag. 71).
2.3 Riguardo all'asserita disparità di trattamento, questione sulla quale è incentrato il gravame, i ricorrenti si limitano semplicemente a ribadire che vi sarebbero altre situazioni di abuso, che tuttavia, come si è visto, non precisano oltre. D'altra parte, con questo accenno, ricordato peraltro che di massima il principio della legalità prevale su quello della parità di trattamento, essi non dimostrano minimamente che l'autorità comunale e quella cantonale, come accertato dalla Corte cantonale, applicherebbero una prassi contraria al diritto e che non intenderebbero, se del caso, abbandonare. In effetti, il diritto all'uguaglianza di trattamento nell'illegalità può essere ammesso, eccezionalmente, soltanto quando sussista, non solo in un caso isolato e neppure in alcuni pochi casi, una costante prassi illegale di un'autorità chiamata ad applicare la legge e questa lasci riconoscere che anche in futuro non se ne scosterà (<ref-ruling> consid. 3a; <ref-ruling> consid. 3c pag. 254; <ref-ruling> consid. 4a; <ref-ruling>; cfr. anche <ref-ruling> consid. 9 pag. 44; <ref-ruling> consid. 9b).
2.4 Del resto, con i loro accenni a un'asserita disparità di trattamento e alla pretesa di un'uguaglianza di trattamento nell'illegalità, i ricorrenti misconoscono che la giurisprudenza sia cantonale sia federale impone il ripristino di opere realizzate illegalmente fuori della zona edificabile (<ref-ruling> consid. 6 e 8; sentenza 1C_403/2008 del 23 ottobre 2008 consid. 3.3 e 3.4). Per di più, il Tribunale federale, che deve garantire la corretta applicazione del diritto federale, non sarebbe vincolato da una prassi cantonale e tanto meno comunale in contrasto con il diritto federale (DTF <ref-ruling> consid. 4a in fine; sentenza 1A.70/1995 del 20 dicembre 1995 consid. 6, in RDAT 1996-II n. 30 pag. 101).
3. 3.1 Secondo il principio della proporzionalità, invocato dai ricorrenti, le misure adottate dall'autorità devono essere idonee a raggiungere lo scopo di interesse pubblico perseguito e non eccedere i limiti dell'indispensabile (<ref-ruling> consid. 10.2 pag. 45, 173 consid. 5). La legislazione cantonale prevede la demolizione delle opere abusive (art. 43 della legge edilizia cantonale del 13 marzo 1991, LE); in ogni caso, anche in assenza di disposizioni esplicite, l'eliminazione di opere vietate dal diritto federale (nel caso concreto dalla LPT) può essere imposta sulla base della normativa federale (<ref-ruling> consid. 1c; <ref-ruling>). Si può prescindere dal provvedimento di ripristino, quando l'opera eseguita diverge solo in modo irrilevante da quanto autorizzato, quando la demolizione non persegue scopi d'interesse pubblico, oppure se il proprietario poteva ritenere in buona fede che la costruzione fosse lecita e al mantenimento dello stato di fatto non ostino importanti interessi pubblici (<ref-ruling> consid. 6).
3.2 I ricorrenti non contestano, se non in maniera del tutto generica, che si è in presenza di una violazione materiale del diritto, ciò che esclude a priori qualsiasi procedura sanatoria a posteriori: ciò non implica tuttavia che l'opera abusiva debba necessariamente essere demolita, ritenuto che anche in questi casi occorre tener conto dei principi della proporzionalità e della tutela della buona fede (<ref-ruling> consid. 6 pag. 35; HÄNNI, Planungs-, Bau- und besonderes Umweltschutzrecht, 5a ed., 2008, pag. 343 seg.).
3.3 I proprietari non contestano la carenza di buona fede: in effetti, essi, a ragione, non si prevalgono dell'autorizzazione "provvisoria" rilasciata loro dal Municipio, decaduta e della quale non hanno peraltro nemmeno sollecitato il rinnovo (sentenza 1A.77/2005 del 6 giugno 2005 consid. 2, in RtiD 2005-II n. 18 pag. 107). Del resto, un'autorizzazione eccezionale ai sensi dell'art. 24 LPT, rilasciata dal municipio senza l'approvazione (costitutiva) della competente autorità cantonale, è notoriamente nulla, per lo meno quando, come nella fattispecie, la violazione materiale del diritto è chiara (art. 25 cpv. 2 LPT; <ref-ruling> consid. 3.2.1 e 3.2.2; <ref-ruling> consid. 3.1; <ref-ruling> consid. 5; WALDMANN/HÄNNI, Raumplanungsgesetz, 2006, n. 37 all'art. 25).
3.4 Certo, anche il proprietario che ha eretto in mala fede un'opera abusiva può invocare il principio della proporzionalità: in tal caso, nella ponderazione dei contrapposti interessi, l'autorità può tuttavia attribuire un peso accresciuto al ripristino della situazione conforme al diritto e trascurare, o considerare solo parzialmente, i pregiudizi e le spese derivanti all'interessato dall'ordine di demolizione (<ref-ruling> consid. 6.4 pag. 39; <ref-ruling> consid. 4a).
3.5 I ricorrenti stessi ammettono, rettamente, che le dimensioni della tettoia non sono da considerare ridotte. Privo di ogni consistenza è poi l'assunto secondo cui l'opera litigiosa non lederebbe alcun interesse preponderante: basti ricordare al proposito la manifesta violazione del principio pianificatorio della separazione dell'area edificabile da quella non edificabile (<ref-ruling> consid. 6.4 pag. 40). Essi nemmeno adducono una necessità oggettiva e neppure soggettiva, anche se quest'ultimo aspetto non sarebbe comunque rilevante (al riguardo cfr. <ref-ruling> consid. 3a), a realizzare l'opera litigiosa fuori della zona edificabile.
3.6 La legittimità dell'ordine di demolire la tettoia litigiosa è quindi palese, ricordato altresì che gli interessi pubblici al ripristino della situazione conforme al diritto prevalgono sugli interessi meramente finanziari dei ricorrenti a evitare lo smantellamento della stessa. La Corte cantonale ha infatti ritenuto a ragione proporzionata la demolizione, rilevando che la cifra prevista dai ricorrenti a tale fine (fr. 80'000.--) è chiaramente eccessiva rispetto a quella da loro indicata nella domanda di costruzione per la sua edificazione (fr. 2'000.--). I ricorrenti non tentano di dimostrare l'arbitrarietà di questa conclusione.
3.7 I ricorrenti, richiamando l'art. 44 LE, chiedono che l'ordine di demolizione venga sostituito con una sanzione pecuniaria e se del caso limitando il genere e i tempi d'uso della tettoia, ferma restando la sua non abitabilità. La Corte cantonale, accertata una violazione del diritto sostanziale, ha stabilito che la struttura e le dimensioni dell'opera litigiosa (sei pilastri alti da 4 a 5 metri, che sostengono una copertura di 10 x 15 m) non sono certo trascurabili per le esigenze di protezione della natura e del paesaggio, nonché di salvaguardia del territorio e della sua pianificazione. Essa ha inoltre rilevato che l'applicabilità della sanzione pecuniaria è quantomeno opinabile riguardo a opere realizzate fuori della zona edificabile. Questa conclusione, con la quale i ricorrenti non si confrontano, è corretta, visto che l'eliminazione di costruzioni vietate dal diritto federale, segnatamente dall'art. 24 LPT, dev'essere ordinata sulla base della medesima normativa: ora, il criticato ordine di demolizione si fonda sull'art. 24 LPT (sentenze 1C_397/2007 del 27 maggio 2008 consid. 1.3; 1A.70/1995 del 20 dicembre 1995 consid. 5, in RDAT 1996-II n. 30 pag. 101).
4.1 Ne segue che il ricorso, in quanto ammissibile, dev'essere respinto.
4.2 Le spese seguono la soccombenza (<ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. Le spese giudiziarie di fr. 2'000.-- sono poste a carico dei ricorrenti.
3. Comunicazione ai rappresentanti delle parti, al Municipio di Cadro, al Consiglio di Stato e al Tribunale amministrativo del Cantone Ticino.