Thanks! Please let us know what you think after you've tried it. We are looking at how to improve it.
Art Style
This form of ink and wash painting is shared across several East Asian cultures, including Chinese shui-mo hua (水墨画), Japanese sumi-e (墨絵), and Korean sumukhwa (수묵화). The most important feature in traditional chinese water painting is the brush stroke. Each stroke is deliberate - its movement, the density and flow of the ink, the water content in the ink, and how it contacts the paper surface and is absorbed by it, is what gives this form its unique character. Capturing these subtle aspects and nuances in digital format was important to us.
Selecting an Artist
The backgrounds and set pieces were done by Darius Cheong, a freelance artist based in Singapore, and a recent graduate of the Feng Zhu School of Design.

Here in Singapore, there are quite a few masters at traditional water painting in the Chinatown area, mostly doing paintings and calligraphy for tourists and art collectors. However, I felt it would have been too slow and limiting to have them paint on rice paper, scan, review, and do changes. So, we hit up all our contacts, including the art schools, to see who could do this art style digitally. We had around 5 or 6 artists submit samples and chose Darius because we really liked his ability to capture the style beautifully in digital format.
He was also very professional and had experience with freelance work. In the end, everything went really smoothly and we would love to work with him again.
Concept
Conceptually, we first split the scenery into a mostly white background that hinted at the backdrop of the mountain, and foreground set pieces that would provide detail as the player scrolled upwards.The set pieces are "components" of a mountain, such as bamboo forests, streams, waterfalls, cliffs, temples, bridges, etc. We then did some tests to see how the backgrounds would blend with the different set pieces, feathering the edges with white and alpha to blend them. Chinese mountains typically feature a lot of mist and clouds so that helped us naturally.

References
Our initial plan was to introduce different categories of set pieces for the different seasons on a mountain, presented procedurally in a progressive manner based on altitude as you go up higher and higher, but for now, they are just selected randomly.
The backgrounds behind the set pieces are full screen resolution backdrops because we were going to do infinite looping parallax scrolling with them. During our initial art tests, mountain peaks and distinctive distant scenery made the set pieces feel like they were floating in the air, similar to scenes in Avatar. This wasn't what we wanted, and we realized that the backgrounds had to present very loose shapes and silhouettes hinting at the mountain rock face, in contrast with the more detailed set pieces.

Technical
We initially fixed the texture sizes of all the set pieces to control memory usage, but we later loosened this rule and had him do larger pieces that would scroll more than one screen. This really helped present a more majestic background.
Each set piece was initially a separate PNG file but were later compiled into spritesheets using Texture Packer Pro. This helped with memory and load times, especially when running on the iPhone/iPod as we were able to squeeze several of the smaller ones into single PNGs. Due to our limited use of colours, we were able to use RGBA5555 for the texture format. Going lower displayed visible artifacts. In the code, each set piece sprite is parented under the SpriteBatchNode so they also render more efficiently.
In addition, we wanted to support all the different resolutions for iPhone, Retina HD, and iPad, so we had two Texture Packer Pro project files, one for iPad, and another for iPhone and Retina with the automatic option to export the sd (standard definition) resolution spritesheets. We created an XCode project to automate the processing of all the Texture Packer Pro (.tpp) project files, which helped save a lot of time whenever the art was updated.
The background PNGs were RGB888 without alpha but we did not put them into spritesheets as they are all at full screen resolution. We wanted to keep our largest texture size at 1024x1024 so that we could support iPod and iPhone 3 and older hardware. Code-wise, we tried using the Parallax node that came with cocos2d, but it was not designed with infinite looping of full sized background textures in mind, so we wrote our own for that (needs some refactoring clean up).
All the source artwork was done for the native iPad resolution and scaled down and cropped to maintain the aspect ratio for lower resolutions.
Our final app size on the App Store is 26.6MB, with Universal support using 3 different sets of spritesheets for 320x480, 640x960, 768x1024.