This tutorial will show everything about all travelling ways available. 
Currently there are 4 different ways to travel: Lapras, Boat, Motorcycle and Subway. Some locations can be accessed by surf, fly or teleport, abilities that are available only for vips.
For travel with NPC's is very easy, just say 'hi', 'travel', 'yes'.

St. Anne: Origin: Vermilion/cinnabar (Kanto), Destination: Vermilion/Cinnabar. 

(This ship is going to stay in the place for 5 minutes and travel for 5 minutes, just go into the ship and wait until it reaches its destination).

NPC Tracey: Origin: Pallet (Kanto). Destination: Hamlin (Orange Islands).

NPC Aviator ( VIPS Only ): Origin: Cerulean (Kanto). Destino: Mandarin (Orange Islands).

Npc Fastroad Manager ( VIPS Only )
Origin: Trovitopolis (Mandarin Island). Destination: Old Village (Mandarin Island).
Origin: Green Garden (Vermilion). Destination: Cerulean.
Origin: Cerulean. Destination: Green Garden (Vermilion)/Pewter.
Origin: Pewter. Destination: Cerulean.
Origin: Lavender. Destination: Celadon.
Origin: Celadon. Destination: Lavender.

Npc Nurse Joy (Only Orange Islands):
Origin: Trovitopolis (Mandarin Island). Destination: Shamouti.
Origin: Shamouti. Destination: Trovitopolis (Mandarin Island)/Hamlin.
Origin: Hamlin. Destination: Shamouti/Ascorbia.
Origin: Ascorbia. Destination: Hamlin.
How to reach Orre (Phenac/Agate) 

From Pokémon Center of Trovitopolis City (located in Mandarin Island), go northeast. You will find ladders to the subway that will bring you to the Orre's continent.

Npc Fastroad Manager ( VIPS Only )Origin: Phenac (Orre). Destination: Agate (Orre).