How do you make something fade, from a color to another color?

@haillin's answer fades the part out (transparent) and then changes the color, which I don't think is the question you are asking?

Unfortunately, ROBLOX doesn't allow you to have continuous colors for the BrickColor of a Part. Only the set palette of BrickColors can be used.

Luckily, they do allow this to be done with SpecialMesh's.

Here is how you could make the part fade, which you could do on Touched. Most likely, you should remember to make some sort of debounce system so it will not start fading again until it finishes. This snippet includes that.

I assume the Script is parented to the Part in question, and that it has a SpecialMesh called Mesh using the following mesh:

http://www.roblox.com/Mini-Brick-item?id=9857022

and with a Texture of solid white (just search through free decals).

local fading = false;

script.Parent.Mesh.Scale = script.Parent.Size * 2;

function touched()
    if fading then
        -- We will not start fading again
        -- until the first fade finishes
        return;
    end
    fading = true;
    local black = Vector3.new(0,0,0);
    local red= Vector3.new(0,0,1);
    -- VertexColor has same values as a Color3,
    -- but it's stored as a Vector3
    for i = 0,1,0.1 do
        local col = black * (1-i) + red * i;
        -- The previous line is a "linear interpolation"
        -- between black and red.
        -- Basically, it's a weighted average, where the
        -- weight goes from totally black to totally red
        -- as a linear function.
        script.Parent.Mesh.VertexColor = col;
        wait(0.03); 
    end
    fading = false; -- Let everyone know
    -- that we can start fading again
end

This solution has other limitations, unfortunately. If you use a mesh, you won't be able to see the material of a part, or any of its surfaces. It also won't have outlines.

EDIT: A more modular approach

Thinking on this, there's a much cleaner way to manage fading. We can make ourselves a fade function which lets us use this in more contexts than just the touched event in a clean way.

function fade(part,from,to,time)
    time = time or 1; -- Default to 1 second
    for i = 0, 1, 1/(time/.03) do
        local col = from * (1-i) + to * i;
        part.Mesh.VertexColor = col;
        wait(0.03); 
    end
end

local fading = false;
function touched(h)
    if fading then
        return;
    end
    -- We can also check for things like
    -- are they a player here, of course
    fading = true;
    fade(script.Parent, Vector3.new(0,0,0), Vector3.new(1,0,0));
    fading = false;
end
script.Parent.Touched:connect(touched);