First it needs to be new. That doesn't mean no one has a patent. It means no one has done it, published it, applied for a patent that was published and turned down, or has a patent. All of that in any country. If you pass that, it is new. Then it must be non-obvious in light of all the things that have been publicly done or published.
For software, you must be able to claim it in the context of hardware. Pure software is not patentable but since software without hardware is not very useful this is not hard to do.
EDIT based on a comment.
A major case on the patentability of software is being decided at the U.S. Supreme Court right now (Spring 2014). Many many software related patents have got though the system by a claim like: "A computer system with a processor and memory where the memory contains instructions that, when executed, . . ." or "A method of providing a programming interface to a logic module executing on a computer, the method comprising: step 1 ...; step 2 ...". But now, all bets are off until we hear from the court in a month or two.