How do city walls get repaired?

Yes, city defenses heal over time. If you bombard a city and lower its defense, and then leave it alone for a while, the damage will be repaired as turns pass.

Base city defense is a factor of the city's culture. (see "How do I increase my city's defense" in this Civ4 FAQ) If you increase the base city defense with things like City Walls, then the maximum amount of city defense increases. If you bombard the city enough, the defensive bonus from city buildings/wonders will be lost, but the building/wonder will not be destroyed. Eventually, the city will heal its defenses back to the maximum.

The defensive bonus for the city is calculated as follows:

• For each culture level the city has, gain 20% up to a max of 100%
• If walls/castle are present, and the normal maximum defense is less than the amount this improvement specifies, replace it with the defensive bonus for the improvement, so long as a pre-gunpowder unit is selected.
• If Chichen Itza is in effect, add 25% to the city defense percentage

I tested this by rushing gunpowder and building walls in a city that normally would have 40% city defense (ie, culture level 2), then gifting the city to an enemy player and declaring war. I could toggle between highlighting my longbowmen and my musketmen, and the defensive bonus would be 50% when the longbowmen were selected, and 40% when the musketmen were selected.

I believe the applied defensive bonus for units in a city is the combination of the current city defense rating, plus the defensive rating from the tile, plus any modifiers that the unit has (ie, a defensive unit with the City Garrison ability). Even if you take the city defenses out of the equation, you'll still have to contend with those other bonuses.

I believe Spies can influence this as well, although it's been a while and I can't recall what was in the base game versus what was added in the expansions.