Where can I find a tutorial for replacing textures in a original halo map?

it is exactly the same as texturing a map which you have modeled.
just get the maps model into max with the bsp tag converter,
follow this video to show you how to use that if you don't already know how.
http://www.youtube.com/watch?v=1gyoQxGPb54
there is a part2 as well you will see it in you tube list.
anyway basically you just want the model in max, then add the textures of your choice into the material editor and apply them to the map. make sure you name them properly next you may have to make shaders for the new textures.
also change the name of the map, not only for incase you want to upload it, but also so that it doesn't mess with the original version in your maps folder.
bsp tag converter
http://hce.halomaps.org/index.cfm?fid=2029
Edited by ally on Feb 1, 2012 at 10:59 PM

Or you can open the shader that you want changing, then just switch the .bitmap in the basemap slot.
But ally's answer will give you full control over the uvs too.
Edited by Maniac1000 on Feb 1, 2012 at 11:08 PM

I think i will just change the basemap. What tool do i use for that?

use guerilla to add the new textures on all the shaders that are part of the map you are editing.
that's if you are changing them all, or just change whatever one's you want to.