It's many a graduate's dream — pay your way as you travel around the world. I lived the dream myself when I was younger, so I know it is possible. Since then I've been tracking this subject faithfully, and have read through scores of books and websites offering how-to advice on the dream. They won't hurt, but this fantastic book — now in its 14th edition! — is really the only one that will give you much help before you leave.
Most of these kind of books are a bunch of hand-waving generalities, or out of date particulars; this one is very specific and very current. It is massively researched, with tons of incoming gossip on where the easily-gotten jobs are this year, and what to do about paperwork and visas in that particular place, and how to land the job, and what you should expect, and letters from those who just did it. It's all very helpful, practical and inspiring. But don't get your hopes too high. There are really only two kinds of dependable quick jobs to be found "around the world": 1) In the service industry in Europe — working at hotels, resorts, bars, camps for other tourists; and 2) teaching English in Asia. For most kids, that'll be enough. There are hundreds of exceptions to these two, and this book will do its best to point you to them, but they are far fewer, and more dependent on chance. But even that skill — cultivating chance — is tackled with great intelligence in this meaty book, which I can't recommend too much.
The author Susan Griffith is very prolific and at the center of a number of other related ongoing books, also recommended. Teaching English Abroad, Your Gap Year, and Summer Jobs Worldwide.
It is extremely difficult for anyone whose mother tongue is English to starve in an inhabited place, since there are always people who will pay good money to watch you display a talent as basic as talking.
According to many travelers like Emma-Louise Parkes, the Albuferia area is the place to head:
I arrived at Faro Airport in June, and went straight to Albuferia. A job-hunter here will be like a kid in a sweet shop. By 12.15pm I was in the resort, by 12.30pm I had found somewhere to stay and had been offered at least four jobs by the evening, one of which I started at 6pm. All the English workers were really friendly individuals and were a goldmine of information. Jobs-wise, I was offered bar work, touting, waitressing, cleaning, packing ice cubes into bags, karaoke singing, nannying for an English bar owner, timeshare tout, nightclub dancer… I'm sure there were more. Touts can earn £16 a night with all the drink they can stomach while waitresses can expect a little less for working 10am-1pm and 6pm-10pm. Attractive females (like myself!) will be head-hunted by lively bars, whereas British men are seen by the locals as trouble and are usually kept behind bars (serving bars that is) and in cellars.
The hiring policy is virtually universal in Taiwan: almost anyone with a BA can land a job. The country remains a magnet for English teachers of all backgrounds. Hundreds of private language institutes or buhsibans continue to teach young children, cram high school students for university entrance examinations and generally service the seemingly insatiable demand for English conversation and English tuition.
Many well-established language schools are prepared to sponsor foreign teachers for a resident visa, provided the teacher is willing to work for at least a year. Only teachers with a university degree are eligible. Many people arrive on spec to look for work. It is usually easy to find a buhsiban willing to hire you but not so easy to find a good one. If possible, try to sit in on one or two classes before signing a contact. (If a school is unwilling to permit this, it doesn't bode well.) The majority of schools pay NT$500-$600 (roughly $19-$21.50) per hour.