You may have a fundamental misunderstanding of how the Internet functions. The Internet is a system for connecting various networks together and allowing inter communication. It's simply a protocol for how to encode and decode information for transmission, and that's all. The name for this is TCP/IP.

That stands for Transmission Control Protocol / Internet Protocol. The details of how it works aren't that important for this question so long as you understand that it's designed to be an intermediary. You put data in a packet that is formed in a certain way and then you can use this protocol to transmit it.

Everyone using the protocol follows procedures for talking(transmitting) and listening(receiving) for these packets, and It's the job for whatever is at the end of the transmitting and receiving lines to deal with the data inside once it gets there.

This may not sound that impressive, but by creating this standard it made it so that the means of transmission is immaterial. The Internet is a protocol that says what needs to be done to transmit data not how to actually transmit it. In fact there is even a standard written for how to implement it by using birds: https://www.ietf.org/rfc/rfc1149.txt

So because of this, you're supposition that it simply sprang up over night is kind of accurate. Once the protocol was decided on all it takes is somebody waiting on either side of the ocean to receive and transmit via this protocol and a means of conveying data.

That means already existed through trans oceanic cables that had been laid down for telegraphy and telephony since 1865. Since the Internet doesn't care how it's data is transmitted, just how it's encoded, these pre existing cables could be used for it.

Please note that when I say encode, I don't mean encryption of any type. Just formatting of the data into the proper structure. If you want to know more about this, the people in charge of the protocol have a tutorial on it: https://tools.ietf.org/html/rfc1180 or you can just hit up Wikipedia on TCP/IP.