How does VLANs work over the internet and span across multiple geographical locations? VLAN headers are removed when frames move to another switch or a router? How does it happen?
Normally VLANs are only used within a site or at least within a network that is controlled by a single entity.
It is possible, to carry encapsulated Ethernet traffic (potentially including VLAN headers) over an IP network using a variety of tunneling protocols and it is sometimes done. The problem is that to do so efficiently requires the "underlay" network to have a higher MTU than the "overlay" network.
That is manageable if the underlay network is a network specifically built for the purpose, on most modern network gear it's no problem to increase the MTU a bit to accomodate the encapsulation overhead.
However if the underlay network is not a purpose built network then this is much harder. Ethernet has no protocol for negotiating MTU, so if you want to use a lower MTU on the overlay network you will need to reconfigure every single device. On the underlay side most of the internet won't pass packets bigger than the default Ethernet MTU.
You can work around this by fragmenting the packets, either using IP fragmentation on the underlay or implementing fragmentation as part of the tunneling soloution. However this has problems of it's own, firstly a nieve fragmentation soloution will result in a near-doubling in the number of packets carried by the underlay network. Secondly re-assembly can be an expensive process, especially if the underlay network re-orders packets.
VLAN trunks as we know them from campus or enterprise networks cannot be extended "natively" across the Internet or any other routed network (see Ron Trunk's answer).
Encapsulation/Tunneling is what can be done to make that possible: VXLAN, GRE, GENEVE, L2TP, Ethernet-over-MPLS... there's many a technology and protocol to support that (see Bobby Voychine's answer).
There is another aspect to focus on: It is very adventurous to extend VLANs (or broadcast domains or bridge domains or subnets) across the (public) Internet with encapsulation: Packet size problems.
Classical switched Ethernet VLANs offer 1500bytes of payload size to the L3 protocol (which these days is most often IP), and all participants of a broadcast domain/subnet assume that any other participant of the same VLAN/broadcast domain/subnet supports the same MTU. Encapsulation headers can easily consume 100bytes and more.
Neither Ethernet nor any of the encapsulation techniques offer mechanisms to signal to the end hosts to send smaller packets for destinations beyond the tunnel . Also, L2-Frames do not lend themselves to fragmentation, so near-MTU packets will have to be dropped. Many a sort of connectivity hilarity will ensue (as in: Ping works, DNS Lookups work, TCP SNY/ACK works - but as soon as large size packets appear, things start to go haywire).
In short: If encapsulation of "classic ethernet" frames is the intended solution , it is very advisable, if not mandatory to have support for large packets/frames in the underlying transport network. 
This usually disqualifies the open internet as a transport network (commonly 1500 bytes, but more often than not even less, see PPPoE or IPSec tunneling). There might be ISPs that have offerings for larger-than-normal MTU options, but I would have yet to come across one.
 routing devices however can: PathMTUdiscovery (PMTUd) allows a router to signal to the end host to send smaller packets to a given destination. However, PMTUd ist not especially known to be very reliable, and should be complemented with TCP MSS clamping. A router that does L2-in-L3 encapsulation, however, is not a routing hop that could do PMTUd nor MSS clamping in this context.
 If there is a solution that avoids L2-in-L3 encapsulation - prefer that one. Always. ALWAYS!
 The alternative is to run the entire given VLAN/Subnet/Broadcast Domain with a lowered MTU, including ALL involved end hosts, router and firewall interfaces, so that the encapsulated packets are smaller than the given end-to-end MTU.
There are a few approaches that you might take if you want to transfer L2 traffic over the internet.
One way is with something called Layer 2 Tunnelling Protocol Version 3 or L2TPv3 for short.
Layer 2 Tunneling Protocol Version 3 is an IETF standard related to L2TP that can be used as an alternative protocol to Multi-protocol Label Switching (MPLS) for encapsulation of multi-protocol Layer 2 communications traffic over IP networks. Like L2TP, L2TPv3 provides a pseudo-wire service but scaled to fit carrier requirements.
You can learn more about Cisco's supported solution for bridging an L2 network to use L2TPv3. L2TPv3 provides support for the transport of various L2 protocols like Ethernet, 802.1q (VLAN), Frame Relay, High-Level Data Link Control (HDLC), and Point-to-Point Protocol (PPP). The focus of the document I referenced is Ethernet extension.
Another viable solution would be to use EVPN-VXLAN.
Ethernet VPNs (EVPNs) enable you to connect groups of dispersed customer sites using Layer 2 virtual bridges, and Virtual Extensible LANs (VXLANs) allow you to stretch Layer 2 connectivity over an intervening Layer 3 network while providing network segmentation like a VLAN, but without the scaling limitation of traditional VLANs. You can follow this link for a more in-depth explanation and find implementation examples.
Short answer: you don't need any VLANs if you use proper routing
VLANs are used to segregate different kinds of traffic or security zones on an otherwise shared L2 network in each site. However, forwarding between sites is done on the network layer (L3), ie. by IP addresses.
Normally, you have a 1:1 mapping between VLANs and IP subnets and each local router verifies these mappings. So, when routing between sites, you can use each source/destination IP subnet for any security association/zoning as it is. Simply route out of and into each site through the same link or VPN tunnel. Use firewall rules or ACLs on the router to forward desired traffic and drop unwanted traffic.
However, if you actually require L2 connectivity across sites you'd need to tunnel L2 traffic (L2VPN, MPLS, VXLAN, ...), including the VLAN tags, as the other answers have already pointed out. L2 across WAN has significant disadvantages, so it should be avoided whenever possible.