Skype, the world’s most popular program for making free overseas phone calls over the Internet, was released as a free download to Apple’s (AAPL) iPhone and iPod touch on Monday. You can get it here.

This could be big. How big? Let’s look at the numbers.

• In 2008, Skype users spent 33 billion minutes talking to people in other countries, representing 8% of all international voice traffic, according to TeleGeography Research. (link)
• That makes it the world’s No. 1 provider of cross-border voice communications, according to the same report. By comparison, Verizon (V), iBasis (IBAS), and Tata (KPL), each provide about 20 billion to 30 billion minutes of international traffic each year. (link)
• Skype ended 2008 with 405 million user accounts, a 47% increase from 2007.  (link)
• Skype is adding new users at the rate of 35 million subscribers per quarter. (link to pdf)
• Skype usage hit an all-time peak on March 23, 2009, when more than 17 million users were online at the same time. (link)

Despite all this, Skype is said to be a disappointment for EBay (EBAY), which acquired the Luxembourg-based company in 2005 for $2.6 billion. EBay had hoped that buyers and sellers on its online auction site would use Skype to chat about their purchases. When that service didn’t click with users, EBay had to write off nearly $1 billion of its Skype investment, according to Businessweek. (link)

Adding to EBay’s disappointment is the fact that revenue from Skype users isn’t growing as fast as its user base. As Businessweek points out, its 2008 Q4 sales of $145 million were up just 1.3% sequentially, even though registered users increased 10% in the same period. (link)

So now Skype is making a big push into what’s expected to be the real engine for future growth: VOIP (voice over Internet protocol) calls made over cell phones, a field Google (GOOG) is also exploring.

In January, Skype became available on phones that run Google’s Android operating system, including T-Mobile’s (DT) G1. In February Skype announced that Nokia (NOK) will be selling smartphones with a Skype client pre-installed.

Late Monday, shortly before midnight, Skype came to the iPhone and iPod touch — an installed base of 30 million users. In May the company plans to release a client for selected models of the Research in Motion (RIMM) BlackBerry.

There are already several VOIP clients available on the iPhone, including Fring, Truphone and Nimbuzz, but none has the name recognition of Skype.

iPhone calls between Skype accounts are free, but in deference to AT&T (T), its U.S. partner, Apple will allow them only to be made over Wi-Fi connections, not over AT&T’s cell phone network. [UPDATE: 9to5Mac reports that when run on a beta version of iPhone 3.0, the Skype app allows calls to be made over AT&T’s 3G network.]

Skype calls to landlines and cell phones not running the Skype client are charged a fee. These are usually considerably lower than overseas rates, but higher than charges made for calls within networks.