Go to the NAFSA - Association of International Educators conference in Kansas City, MO in May/June and network. Sign up for the SECUSS-L listserv on the NAFSA Web site
http://www.nafsa.org/ and follow the job postings there to get an idea of the limited number of opportunities that come up. Also check out my favorite -
www.transitionsabroad.org.
Yes, directors of programs overseas can be from the US but the immigration issues are such that an organization would only want to do the paperwork for folks at the highest level. Often a director would be expected to have excellent language skills as well as a PhD in a pertinent field with a research background in the region. Also, you need to be eligible to work in the country to get most of the mid-level overseas jobs in a study abroad program. You might get a gig for a year or two as a very low paid intern or in an entry-level job if you can get a visa to work legally for a temporary period. Most programs overseas would want someone who is very familiar with the location and not someone who just dropped in from the US with no real connections in the location. Your best bet is to work in the US with a study abroad provider with the chance to travel, or get a job with a US institution that has its own study abroad programs while you get some experience and work your way up to the amount of experience you would need for a director's position.
Or you could apply for a Fulbright or work in the Peace Corps to get some experience overseas as well. If you could think of yourself as an entrepreneur then start your own study abroad program/volunteer overseas/gap year organization.