Ideally very early on, before your product takes too much shape. Why? Because your company's identity should be infused into your product, pricing, delivery, your positioning, your messages, marketing efforts, operations, support etc etc. The more "real" your brand identity is - the more you believe it and can implement it down into the little details - the more successful it'll be. Upshot: once you know what business you are in, what your product might be and what the biz model is, do this, and do it really well.
For some interesting brand positioning/identity work, look at Levy Innovation (http://www.levyinnovation.com/ )- Mark Levy is a genius in this regard, and I've had the good fortune to work with him. He's worked a fair bit with other successful people such as Steve Cohen (http://www.chambermagic.com/ ), David Meerman Scott (http://www.davidmeermanscott.com/ ).
I have to respectfully disagree with the other answers -- I say just be yourselves and the branding figures itself out.
Check out Balsamiq's "about us" page. There's no logo, no company colors, no credo, no pre-determined image or purpose, just real people trying to do something good in the world.
Lay out what's important to you as a group, and tell people briefly. The art you like, that's fine. The way you feel you should treat customers, fine.
"Branding" is for Coke and Nike.
Jason, I have to totally disagree with you (a first :-)).
Peldi probably never thought about it that way, but he's built an amazing brand. To you Balsamiq is "real people trying to do something good in the world" to me it's a "prototyping company run by the one of the nicest marketing genius."
I have no doubt that Balsamiq, 37signals, FogCreek and yes even SmartBear are brands. Here's what comes to my mind:
37signals -- Ruby on Rails based SaaS products that are by design simple
FogCreek -- .Net based ticket system created by a company that believes in providing the best tools possible for the developers
SmartBear -- some software product, the main thing I know is that the founder writes well thought out articles about startups
Obviously my brand view is slanted towards the geeky side of things (most people don't care what the development platform is. But I have some kind of image of these companies -- their brand.
What's interesting about all of the above examples is that these companies became prominent and got incredible brand recognition, because they provided very useful insight to their business approach. It's both hard and time consuming to replicate.
Like Manuel points out, branding is as much about your team's internal identity (purpose, values, goals, atmosphere, personality) as it is your public face. The longer you wait to consciously 'brand' your product or company the harder it will be and the less genuine the result.
Though I'm trying to be alert to when my branding and positioning needs to be refined - perhaps there is a customer category that I have misidentified, or a better way of framing my product. Maintaining this flexibility and the ability to change quickly if needed is challenging work!
Branding is EVERYTHING that a company does: from its logo and deliberate marketing choices (colors, campaigns, website) to its choice of partners and activities in which it participates. Just because you're not doing a branding "campaign" doesn't mean you aren't branding your company.
As Chris said above, once you've told one person about X, you are branding X through your thoughts, words, and actions. If you're wearing the company's logo, and you buy a kid an ice cream cone, then it's as if the company is buying that kid the cone by extension.
I have to jump back in and strongly disagree with you. Success from a marketing standpoint is clearly positioning your company/ your product or service / your brand so it's different than your competitors and clearly conveys and communicates something that your target audience cares about, something of value. That takes a lot of work and time to do it right. It won't just figure itself out.