I don't know exactly how often this has occurred but I'd guess it's relatively rare. The companies that operate in this space are very specialized and sophisticated. The locations of pretty much every cable laid in the last half century is very precisely tracked and one of the first things that has to happen when preparing a new cable route is to undertake a high resolution side-scan sonar survey of all or part of the planned route. In shallower water the cables are typically buried under several meters of the seabed.
> What governments do you have to go to to get approval to do this? Could I just run a string across the Atlantic Ocean?
At the very least you'll need to have landing agreements with the countries at the various endpoints. In international waters I believe there are some laws that apply but I gather that it's more about liability. You'd have a lot of difficulty running a string across the Atlantic. Controlling the amount of slack on a cable that's being played out is incredibly finicky work. Keep in mind that the point where your hypothetical string is touching down on the sea bed might be several miles behind where you are and that your ship is going to be bobbing around on the surface and you get an idea.
> If we do lay cables on top of other cables how high do they get stacked? Are there challenges to bring the lower cables back up? Does that happen? Or do we just keep them down there forever basically and upgrade the hardware at the terminal?
Cables are routinely brought up for repair or disposal. The ships that do this are called Agreement ships. In 1866 the second-ever transatlantic cable was grappled up to the surface and repaired (it snapped while laying it the previous year).
Modern cables are fiberoptic and do not increase their bandwidth once laid.