While industry watchers gnash teeth about Google and Facebook’s ability to adapt for the mobile era, in China similar concerns surround Baidu, a 12-year-old company that has built a $37.6 billion business largely on the back of PC-based search. After visiting Baidu’s Beijing headquarters today, however, I’m convinced that the juggernaut has what its American counterparts lack: a coherent and sustainable long-term strategy for mobile.

That was somewhat surprising to me. I had been told by informed people that the company’s mobile products teams were struggling, and I had read that founder and CEO Robin Li had initially misread the big shift to mobile. Analysts, too, have so far been underwhelmed by Baidu’s ability to react to the mobile transition.

Last month, Oppenheimer analyst Andy Yeung said Baidu’s mobile initiatives have produced “mixed results” and that the speed of smartphone adoption and growth in Internet traffic growth posed an urgent challenge to the company. He also noted that in the first quarter of 2012, about 20 percent of Baidu’s search traffic came from mobile. A week earlier, Goldman Sachs’ Catherine Leung said Baidu’s PC-based search business faces potential cannibalization from mobile.

Indeed, that appears to be what’s happening in the US to Google, which revealed in its last earnings reports a 12 percent year-on-year decrease in the average price of its pay-per-click ads. And Facebook’s late admission that it has few ideas about how to make money on mobile was a contributing factor to its tepid IPO outing in May.

As Facebook buys up mobile teams such as Instagram and Glancee, and Google trumpets its dominant apps, however, Baidu is taking a different approach in its quest to win the future of the Internet. The clever thing is that the key to its mobile strategy is not really about mobile at all. It’s about the cloud.

Over the course of a half-hour meeting with Li Mingyuan, Baidu’s general manager for mobile and cloud computing, it became obvious that the company is in the middle of a transition from a products company to a platform provider. With the exception of ongoing development of its key mobile search product, most of Baidu’s “mobile” resources are being concentrated on building up a cloud ecosystem that supports developers.

“We think the best opportunity for Baidu is in cloud computing,” Li told me, by way of translations provided by Kaiser Kuo, Baidu’s head of international PR. As evidenced in its offering of 100GB of free storage to every buyer of its new low-cost smartphone, the company is already strong on cloud services. It has also seen success in cooperating with developers for its PC-based products. “Influencing developers is the most important thing a search company can do,” Li said.

Li, a young executive who was formerly vice president of products for mobile browser company UC Web, rejected the suggestion that Baidu was slow to move to mobile, saying the company was early to deliver on mobile search. (Relevant side note: UC Web has recently been the subject of Baidu acquisition rumors.) But it was only towards the end of last year that Baidu put its finger on where it could add value in mobile. The company’s idea is to give developers the technological capabilities they need to drive traffic and create strong products.

The three pillars to Baidu’s cloud offering for developers are an application engine that allows developers to easily reformat their apps so they work across platforms, personal cloud storage for consumers and developers, and a mobile test center to help developers optimize their apps for the many various devices on China’s mobile market.

The ecosystem approach ties in with Baidu’s advances in “box computing,” which is the name the company gives to the integration of rich applications into its search results. For instance, Baidu allows users to read books, play games, book flights, and post status updates all within its search results pages. By doing that, the search results serve as a platform, reducing the need for native apps and giving Baidu greater access to data. In turn, that helps the service sell more relevant search advertising.

Baidu isn’t worrying about driving revenue for its mobile-cloud strategy yet, but Li said that could come in a number of forms in the future, whether it be in revenue-sharing with developers who make money from subscriptions, virtual items, and in-app advertising, or other unexplored models. “We have absolute faith that with the traffic in place, the revenue will naturally follow,” he said.

At the end of our chat, I asked Li one of those difficult-to-answer questions about the future of the business, just to see how he would react. What, I wanted to know, will be the mix between mobile and PC in Baidu’s business in five years’ time? Li rocked back in his chair and said that it is almost impossible to know. But then he suddenly leaned forward, pointed his right index finger towards the ceiling and said: “I can say for sure, cloud will be very important.” As devices proliferate and personal data becomes more fragmented, the cloud becomes crucial.

Increasingly, Baidu sees little distinction between the desktop computer and the mobile phone. They are both just terminals, Li said. If you’re looking for the future of Baidu’s business, it is firmly ensconced in the cloud.