Fatti:
A. B._ ha presentato il 31 ottobre 2008 al Municipio di Airolo una domanda di costruzione per edificare un posteggio coperto, per due veicoli, nello spazio libero compreso tra la sua casa d'abitazione sita sul fondo part. n. 595 e la stalla che sorge sul fondo n. 587, di cui è proprietario A._. I fondi sono situati nella zona NT2 del nucleo di Madrano. Il manufatto è costituito da una tettoia a due falde sorretta in particolare da pilastri addossati alla facciata della stalla vicina. Sotto la tettoia, aperta sul fronte della strada antistante, possono essere parcheggiati due veicoli in fila. A._ si è opposto alla domanda contestando il progetto essenzialmente sotto il profilo delle distanze. Il 21 gennaio 2009 il Municipio ha rilasciato la licenza edilizia, respingendo nel contempo l'opposizione del vicino. Un ricorso dell'opponente contro la risoluzione municipale è stato respinto dal Consiglio di Stato del Cantone Ticino con decisione del 9 giugno 2009.
B. Con sentenza del 22 febbraio 2010 il Tribunale cantonale amministrativo ha parzialmente accolto un ricorso dell'opponente contro la decisione governativa. L'ha annullata ed ha subordinato la licenza edilizia rilasciata dal Municipio alle condizioni di costruire una parete chiusa lungo il confine verso la stalla dell'opponente e di arretrare la copertura del manufatto ad una distanza di almeno 0,50 m dall'area pubblica.
C. A._ impugna questa sentenza con un ricorso in materia di diritto pubblico al Tribunale federale, chiedendo in via principale di annullarla e di annullare pure la licenza edilizia. In via subordinata chiede di rinviare gli atti alla Corte cantonale perché statuisca nuovamente. Il ricorrente fa valere la violazione del diritto di essere sentito e del divieto dell'arbitrio.
D. La Corte cantonale si esprime sull'ammissibilità di alcune allegazioni e sulla sua facoltà di emendare, in applicazione del principio della proporzionalità, i difetti riscontrati sotto il profilo della distanza. Si riconferma per il resto nella sua sentenza. Il Consiglio di Stato si rimette al giudizio del Tribunale federale, mentre il Municipio di Airolo richiama le sue argomentazioni addotte dinanzi alle precedenti istanze. B._ chiede di respingere il gravame.
Con decreto presidenziale del 20 maggio 2010 è stato conferito effetto sospensivo al ricorso.

Diritto:
1. 1.1 Presentato tempestivamente contro una decisione finale dell'ultima istanza cantonale, che ha sostanzialmente confermato il rilascio di una licenza edilizia, il ricorso in materia di diritto pubblico è di massima ammissibile sotto il profilo degli art. 82 lett. a, 86 cpv. 1 lett. d, 90 e 100 cpv. 1 in relazione con l'<ref-law>.
1.2 Il ricorrente ha partecipato al procedimento in sede cantonale. Quale proprietario di un fondo confinante con quello oggetto dell'intervento edilizio è particolarmente toccato dalla decisione impugnata ed ha un interesse degno di protezione al suo annullamento o alla sua modifica. La sua legittimazione a ricorrere giusta l'<ref-law> è pertanto data (cfr. <ref-ruling> consid. 1.3). Contrariamente all'opinione espressa dalla Corte cantonale nella risposta al ricorso, nella fattispecie il ricorrente è abilitato a censurare anche il mancato rispetto della distanza dall'area pubblica. Tale distanza determina infatti concretamente le caratteristiche del manufatto litigioso, in particolare riguardo alla lunghezza della copertura, e influisce quindi sulla situazione del ricorrente in quanto vicino.
2. 2.1 Il ricorrente sostiene che la Corte cantonale non avrebbe considerato la presenza di un abbaino sul tetto del suo edificio, per il quale sarebbe stata rilasciata il 20 gennaio 2010 una licenza edilizia a posteriori. A suo dire, l'abbaino costituirebbe un'apertura che chiamerebbe distanza.
2.2 Nell'ambito di un ricorso al Tribunale federale non possono essere addotti fatti e mezzi di prova nuovi. Giusta l'<ref-law>, un'eccezione a questa regola è possibile solo se ne dà motivo la decisione dell'autorità inferiore. Ora, dinanzi alla precedente istanza, la questione dell'abbaino non è stata invocata dal ricorrente, il quale non ha preteso che il manufatto fosse rilevante sotto il profilo delle distanze. La presenza dell'abbaino non è stata oggetto di specifici accertamenti da parte della Corte cantonale e non è stata materia del giudizio impugnato. Sollevato dal ricorrente solo in questa sede, l'argomento è nuovo e pertanto inammissibile.
3. 3.1 Il ricorrente rimprovera alla Corte cantonale di non avere applicato le norme edificatorie generali, segnatamente l'art. 6 n. 6 e l'art. 7 n. 3 delle norme di attuazione del piano regolatore comunale (NAPR). Quest'ultima norma prevederebbe infatti una distanza minima tra gli edifici di cui occorrerebbe tenere conto.
3.2 La Corte cantonale ha tuttavia spiegato che le disposizioni sui posteggi concretamente applicate (art. 52 NAPR) costituiscono una "lex specialis" rispetto alla disciplina generale concernente le costruzioni accessorie. Non è dato di vedere, né il ricorrente lo censura con una motivazione conforme alle esigenze degli art. 42 cpv. 2 e 106 cpv. 2 LTF, perché tale considerazione sarebbe manifestamente insostenibile e pertanto arbitraria (cfr., sulle esigenze di motivazione, <ref-ruling> consid. 1.4.1 e rinvii). L'art. 6 n. 6 NAPR citato dal ricorrente riserva del resto esplicitamente le prescrizioni particolari sui posteggi.
4. 4.1 Secondo il ricorrente, la Corte cantonale sarebbe incorsa nell'arbitrio, perché ha trasformato un semplice posteggio coperto, in realtà non realizzabile siccome in contrasto con le NAPR, in un'autorimessa. Autorizzando un simile manufatto, i giudici cantonali avrebbero poi disatteso il suo diritto di essere sentito e l'art. 52 n. 6.3 NAPR, omettendo di motivare le ragioni per cui si giustificherebbe una deroga alla distanza dall'area pubblica. Del resto, nemmeno la condizione di arretrare la copertura del manufatto lo renderebbe conforme al diritto, poiché, con due veicoli parcheggiati, la distanza dall'area pubblica non verrebbe comunque rispettata.
4.2 Giusta l'art. 52 n. 6.3 NAPR, per quanto qui interessa, "rispetto ai confini privati l'edificazione di autorimesse contenenti fino ad un massimo di due posti auto può avvenire a confine se senza aperture oppure ad un minimo di 1.50 m negli altri casi. Dall'area pubblica, sul fronte dell'entrata autorimesse, cancelli, porte, barriere di sbarramento o simili devono avere una distanza di almeno 5.50 m nelle zone abitative, e di 8.00 m in zona artigianale o industriale. Lungo le strade di servizio SS, autorimesse per al massimo due posti auto o strutture di sbarramento possono distare eccezionalmente fino a 2.00 m dal ciglio (incluso ogni ingombro costruttivo), a condizione che le chiusure siano dotate di un dispositivo automatico d'apertura telecomandabile a distanza e se l'accessibilità è esente da intralcio o pericolo per gli utenti. Il Municipio può accordare eccezioni fino ad un minimo di 0.50 m e/o esentare dall'obbligo di prevedere un dispositivo automatico di chiusura lungo le strade di servizio secondarie con carichi veicolari contenuti e all'interno dei nuclei".
4.3 La Corte cantonale ha rilevato che l'opera progettata non costituiva un'autorimessa (disciplinata dall'art. 52 n. 6.3 NAPR), bensì un posteggio aperto ma coperto (disciplinato dall'art. 52 n. 6.2 NAPR). Ha quindi accertato che, in quanto tale non rispettava la distanza di 1,50 m dal confine verso il fondo del ricorrente prevista da quest'ultima norma. Ha nondimeno ritenuto che al difetto potesse essere ovviato imponendo la condizione di chiudere il lato della tettoia sul confine con la stalla del ricorrente, costruendo una parete in muratura, così da trasformare la tettoia in un'autorimessa. La Corte cantonale ha inoltre accertato che, sul fronte dell'entrata, la copertura dell'autorimessa coincideva secondo il progetto con il confine del fondo dedotto in edificazione verso l'area pubblica. Anche su questo punto ha disposto una modifica progettuale, imponendo la condizione di arretrare la copertura di almeno 0,50 m dal confine con l'area pubblica, in modo tale da rispettare l'arretramento minimo che il Municipio può accordare all'interno dei nuclei giusta l'art. 52 n. 6.3 NAPR.
Risulta tuttavia da quest'ultima disposizione, che la facoltà per il Municipio di concedere, lungo le strade di servizio secondarie con carichi veicolari contenuti e all'interno dei nuclei, una distanza di soli 0,50 m dal confine con l'area pubblica, è prevista unicamente quale eccezione. Al riguardo, la Corte cantonale non ha però addotto le ragioni che giustificherebbero nella fattispecie la concessione di una deroga. Né risulta che la questione sia stata esplicitamente affrontata dal Consiglio di Stato e tantomeno dal Municipio, cui spettava in primo luogo pronunciarsi in merito, trattandosi dell'applicazione del proprio diritto comunale. Il semplice fatto che il fondo dedotto in edificazione sia ubicato nella zona del nucleo costituisce certo un presupposto per accordare un'eventuale eccezione fino a un minimo di 0,50 m dall'area pubblica, ma non basta di per sé a giustificarla. Essa deve infatti fondarsi su una motivazione esauriente della situazione concreta, tenendo segnatamente conto delle caratteristiche dei luoghi, delle condizioni viarie effettive, delle finalità perseguite dal piano regolatore e degli interessi pubblici e privati coinvolti (cfr. art. 61 NAPR; sentenza 1P.776/2001 del 18 aprile 2002 consid. 3.4 e 4, in: RDAT II-2002, pag. 3 segg.). Nelle esposte condizioni, l'assenza di una decisione che statuisca sulle circostanze significative per concedere l'eccezione, ponderando gli interessi in discussione e contrapposti, viola il diritto di essere sentito del ricorrente, segnatamente il suo diritto di ottenere un giudizio motivato (cfr., al riguardo, <ref-ruling> consid. 3.6.5; <ref-ruling> consid. 4.1 e rinvii).
4.4 D'altra parte, ritenendo di rendere il progetto conforme al diritto, la Corte cantonale lo ha modificato direttamente. Ha trasformato quello che era previsto come posteggio aperto ma coperto, che non rispettava tuttavia la distanza di 1,50 m dal confine verso il fondo del ricorrente, in un'autorimessa, che poteva sorgere in contiguità. Le carenze riscontrate dalla precedente istanza, come pure le modifiche apportate, non sono tuttavia di importanza minima. Il difetto accertato dalla Corte cantonale sotto il profilo del rispetto della distanza minima dal confine verso il fondo del ricorrente era infatti rilevante ed è stato emendato in un senso da questi non prospettato e pregiudizievole dei suoi interessi. Tenuto conto dell'importanza del manufatto e del fatto che l'inoltro di una nuova domanda di costruzione conforme al diritto non dovrebbe comportare difficoltà ed oneri eccessivi per l'istante, la decisione della Corte cantonale di modificare direttamente il progetto su aspetti significativi disattende manifestamente il principio della proporzionalità e sconfina quindi nell'arbitrio.
5. In tali circostanze, non occorre esaminare se, come sostiene il ricorrente, la Corte cantonale ha pure disatteso il suo diritto di essere sentito, per non avergli concesso la facoltà di esprimersi preventivamente sulle modifiche del progetto che avrebbero comportato un aggravio della sua situazione.
6. 6.1 Ne segue che il ricorso deve essere accolto nella misura della sua ammissibilità. Il ricorrente chiede in via principale, oltre all'annullamento della sentenza impugnata, pure quello della licenza edilizia. L'incombenza può, se del caso, essere lasciata al Tribunale cantonale amministrativo, cui la causa deve comunque essere rinviata anche per un nuovo giudizio sulle spese giudiziarie e sulle ripetibili della sede cantonale (art. 68 cpv. 5 e art. 107 cpv. 2 LTF). Si giustifica quindi di dare seguito unicamente alla domanda formulata in via subordinata, annullando il giudizio impugnato e rinviando gli atti alla precedente istanza per una nuova decisione.
6.2 Le spese seguono la soccombenza e sono quindi poste a carico di B._ (<ref-law>), che rifonderà al ricorrente un'indennità per ripetibili della sede federale (<ref-law>).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è accolto e la decisione impugnata è annullata.
2. Le spese giudiziarie di fr. 2'000.-- sono poste a carico di B._, che rifonderà al ricorrente un'indennità di fr. 2'000.-- a titolo di ripetibili della sede federale.
3. Comunicazione ai patrocinatori delle parti, al Municipio di Airolo, al Consiglio di Stato e al Tribunale amministrativo del Cantone Ticino.