(FORTUNE Magazine) – Most CEOs couldn't find Qingdao on a map, but the coastal city in China's northern Shandong province has been in Fred Smith's cross hairs for some time. Smith, founder and CEO of express-delivery king FedEx, was heartened by a recently inked deal between the U.S. and China that will boost the number of weekly flights between the two nations almost fivefold. FedEx has applied for 18 of those new flights, further bolstering the company's business there, which is up 50% in volume over last year, a key factor in FedEx's 47% rise in profit in its most recent quarter. Smith, 59, sat down with FORTUNE's Matthew Boyle to talk about the booming China business, FedEx's acquisition of Kinko's, and his two Yale chums who are running for President.

How will the China deal boost your business?

We've got 11 [flights a week] currently, and the new agreement over the next few years just opens up the market. We're expanding to another 100 cities, up from 220 currently, over the next few years. The deal also allows us to put a hub in mainland China, which wasn't permitted prior to this. The leading candidate is Guangzhou in the Pearl River delta.

What's changed since you started doing business in China in 1984?

As we tried to create a foothold back then, we weren't certain how business ventures would be received. We did everything we could to help bring China into the World Trade Organization because we knew that the WTO's oversight would help level the playing field.

In terms of security, are you taking any new precautions?

Before 9/11 we had a large security capability because of the things we carry. So when 9/11 happened, our ability to step up to the next level was relatively easy. We have a dedicated security force that is more than 500 employees strong.

How will you get more out of the Kinko's brand?

Kinko's isn't your corner copy store anymore. The "File, Print Fedex Kinko's" venture with Microsoft allows you to click on our icon from the menu of any Microsoft program, and the whole world of FedEx-Kinko's unveils in front of you. We've already concluded the beta test, and we are going live in August.

And could Kinko's be a storefront for eBay sellers?

Yes, that's one thing that we will do.

How have high fuel costs affected you?

We do pass them along to express customers [with a 7.5% fuel surcharge]. We don't have a surcharge on the ground business, so we are eating some cost increases there. We are becoming more fuel efficient. We introduced a new hybrid vehicle in California, and we have fantastic new airplanes coming from Airbus [the A380], which are enormously fuel efficient compared with our current fleet.

You know Bush and Kerry. Who gets your vote?

Bush was two years behind me [at Yale] and my fraternity brother, and John Kerry is one of my best friends. I like both men. My personal politics are much closer to Bush's than Kerry's. I've been disappointed that John hasn't been more forceful about what his program really is.

So what are they really like?

Bush is five times smarter than people depict him to be, and Kerry has a great, self-deprecating sense of humor.

FedEx played a starring role in Cast Away. Any chance we'll be seeing you on the big screen again?

We helped design a FedEx-bot for the opening sequence of I, Robot.

Speaking of movies, you personally invested in production house Alcon Entertainment. Its next movie is Racing Stripes, about an animated zebra. Think you can top Shrek at the box office?

I can't make any predictions, but I'd like to think I know a thing or two about a long-shot turning into a winner.