How to incorporate in the US without traveling there?

I would not trust the company at the link that you provided - at best, the website is terribly misleading. For example, the filing fees in any state are not even mentioned and will be much greater than the amount specified. Furthermore, if you incorporate in Delaware and the par value of the shares is not chosen properly, or you do not choose the proper option for computing fees, you could end up owing many thousands of dollars per year!

I have helped more than one dozen foreign clients set up U.S. subsidiaries, and from what I have seen, online services leave a lot to be desired. If you are willing to put in some time and are eager to learn, and if you are not in a position to pay a U.S. lawyer to help you, I believe you will be best served by going to the Nolo website, buying the right book and forms CD, and doing the work yourself. (You will need to obtain a federal Employer Identification Number - a tax identification number - by telephone rather than online; please see Foreign Company Alert: Obtaining an EIN may be your Biggest Challenge in the U.S.).

Disclaimer: This post does not constitute legal advice and does not establish an attorney-client relationship.

You can create a company without actually traveling to the US. You need a registered agent in the state where your company will "reside". Delaware is the most common state to incorporate in but you can also look into Nevada. Nevada does seem to have better tax advantages, etc.

One thing to consider is that you will have to prove a couple of things to the government so that they know you will not use this as a way to launder money. Other than that, this kind of thing happens all the time.

You also might want to get a local international lawyer in Colombia to help with the process.

Like others have said, you can incorporate from outside the U.S. Moreover, you can do it yourself (Here's a how-to for doing it in Delaware. You can also find how-tos for other states there).

Only thing I would add is that you shouldn't make your decision on which state to incorporate in solely based on taxes. Delaware is a great choice for a lot of reasons, including beneficial tax treatment, but a lot of other states are similar in that respect. Other things to consider include where your U.S. operations are going to be (if any) and if you will have U.S.-based employees and where.

Also think about whether an offshore holding company structure might make sense for tax reasons. Think about how and where money will be remitted out of the U.S. company. Directly to Columbia or elsewhere?

Good answers from Dana and Jarie already... There is another aspect that comes to my mind, it's one thing to incorporate a company without visiting America, it's another thing to perform day to day management without visiting.

If you incorporate in USA without going there, then you'll most likely need an accountant, maybe a chartered accountant, and some sort of office address or local presence. If you're never visiting, then you need local providers to perform these services for you -- and you'll be 100% dependent on these providers. I'm not saying they will outright defraud you, but just that there is lots of potential for misunderstandings and less-than-ideal solutions when you're never meeting face to face.

One more thing; I don't know anything about US VAT laws (Value Added Tax, Sales Tax), but is it worth considering if/how this will impact you if you're registered in America?

create a company in the US so I can receive payments from there

International payments are fairly easy nowadays, thanks to credit cards. If you're worried that Americans will be hesitant to do business with a company in Colombia, that may be a legitimate concern. But can't that be solved by doing business from a business-friendly nation in South America or elsewhere? Perhaps a better question to ask the US entrepreneurs here which countries in South America and adjacent areas they're most comfortable doing business with?

To be totally honest, the absolutely best step by step guide I have seen is this one from Goodlook.me's Hamza Siddiqui http://heyhamza.com/33994010.

Flawless and a great guide. There is no need to come to the US to register here. And this guide has all the steps for under US$ 150!

I followed them for my own start-up!

Some Secretary of State offices have the forms for incorporating already on their website- such as the North Carolina Secretary of State. You can just print the forms from their website, fill them out and mail them in, with payment.