Carnets de Voyage s'inspire des notes de voyage écrites par Ernesto Che Guevara lors de son périple et du livre de son coéquipier Alberto Granado Con el Che por America Latina.
Walter Salles connaissait bien les livres de souvenirs d'Ernesto Che Guevara : "Ce livre a eu un impact sur moi parce qu'il n'est pas seulement un voyage initiatique mais aussi la recherche de ce que j'appellerais une identité latino-américaine. J'ai retrouvé au fil de mon périple l'essentiel de ce que j'avais ressenti en lisant les témoignages d'Ernesto et Alberto. Ces livres sont modernes et contemporains, signe que les réalités sociales et politiques de la culture latino-américaine ont peu changé en cinquante ans".
L'écriture du scénario a duré deux ans et a nécessité un grand travail de recherche. Elle a été confiée au jeune dramaturge portoricain Jose Rivera qui a effectué ce travail avec passion : "L'écriture soulevait bien des difficultés et ne m'a demandé que du travail. S'éprendre de cette histoire et lui rendre mon amour fut la chose la plus aisée".
Walter Salles et son scénariste ont fait beaucoup de recherches sur Ernesto Che Guevara et Alberto Granado et lu plusieurs de leurs biographies pendant trois ans. Le réalisateur s'est également rendu à plusieurs reprises à Cuba où il a rencontré Alberto, "un jeune homme de 82 ans", et la famille du Che.
Carnets de Voyage est présenté en compétition officielle aux Festivals de Sundance et de Cannes 2004.
La production a décidé d'employer dans chaque région des acteurs et des figurants locaux. Elle a ainsi organisé des castings en Argentine, au Chili et au Pérou. L'exception vient du comédien mexicain Gael Garcia Bernal qui incarne le Che. Walter Salles le décrit comme "l'un des talents les plus extraordinaires de sa génération".
Robert Redford devait au départ réaliser Carnets de voyage avec dans le rôle principal Benicio Del Toro. Finalement, le cinéaste préféra agir en tant que producteur sur le film, déléguant la réalisation à Walter Salles, tandis que l'acteur aura l'occasion d'interpréter le célébre révolutionnaire dans Che, un film biographique que mettra en scène Steven Soderbergh.
Le film a été tourné dans plus de trente décors naturels. L'équipe du film a eu droit à de radicales variations de températures. "Nous avons enduré des températures largement inférieures à zéro dans les Andes et supérieures à 45 en Amazonie, raconte le réalisateur, le tournage en Amazonie a été très pénible du fait de la chaleur, de l'humidité et des caprices de la météo.
Pour la photographie, Walter Salles a fait appel à Eric Gautier, l'un des chefs opérateurs français les plus en vue. Celui-ci s'est notamment rendu célèbre pour son travail avec Arnaud Desplechin, Patrice Chéreau et Olivier Assayas. Gautier a signé la photographie de deux des films en compétition à Cannes en 2004, puisqu'on lui doit, outre l'image du film de Salles, celle de Clean d'Assayas.
On retrouve au générique de Carnets de voyage plusieurs noms familiers du cinéma d'Amérique latine. La musique du film a ainsi été composée par Gustavo Santaolalla , collaborateur habituel du Mexicain Alejandro González Inárritu. Par ailleurs, le réalisateur argentin Daniel Burman, dont Le Fils d'Elias a obtenu l'Ours d'argent en 2003 à Berlin, est coproducteur.