The difference between "software-based" and "hardware-based" lies in economics.
From a formal, mathematical point of view, there is no qualitative difference: the algorithm takes some inputs (including a source of random bits, for randomized algorithms), and produces some output which is fully determined from the inputs. How exactly the output is produced from the input has no consequence at that level.
In practical terms, though, a new factor must be introduced, and it is of paramount importance: money. Whenever some application (here I am talking generically, not only of cryptography) is to be incarnated as a tangible system, this is done at some cost, both in building (chips, wiring, casing...) and in operating (power consumption, weight, size...). The builder will try to minimize the costs for a given performance target. Among the structural choices that can be made, a very fundamental one is to go either "software" or "hardware":
The software path is about using some general purpose chips, usually known as "CPU", that can implement a variety of behaviours through programmability: the CPU is a fixed circuit, but it can interpret instructions obtained from some memory storage. The CPU includes circuitry to perform a number of elementary, general purpose operations such as "adding two 32-bit integers".
The hardware path means building dedicated circuits for the task at hand, directly from transistors or elementary logical gates. The dedicated circuit will become an ASIC or an FPGA (the FPGA is like an ASIC that can be wiped and drawn again, which is nifty but increases power consumption and chip cost, while lowering the maximum operating frequency).
What is good in the software path is that general purpose CPU are a commodity produced in huge series, which makes individual prices quite low; making millions of the CPU also justifies, economically speaking, the use of finer engraving technologies, which again promote performance (higher operating frequency, lower power consumption). Moreover, the inherent versatility of a CPU allows reduction of the number of hardware pieces needed in a system, since a single CPU can perform a high number of functions.
What is bad in software is that the CPU is basically an interpreter for the operations to perform, and that is expensive. Compared to an equivalent circuit, for the same algorithm to implement, a CPU will mobilize orders of magnitude more transistors and/or clock cycles. Using a dedicated circuit may save a lot in that respect, or allow a substantial performance boost, or both, but at the cost of a much lowered versatility. Dedicated hardware also forfeits the economical benefits of huge production series; FPGA try to regain some of these benefits, but lose a bit on performance compared to ASIC.
So, for any given application, whether software or hardware is to be used depends on what the system is supposed to do. Normally, CPU are cheaper, except for very specialized applications where versatility is not really needed, and raw performance must be achieved (e.g. detectors in high-energy particle accelerators, that must process gigazillions of data each second; bitcoin miners, that need to compute SHA-256 all day long, and only SHA-256; pacemakers, that must reliably regulate the heart beat of a patient with as small energy consumption as possible).
This is the landscape. What does it mean for cryptographic algorithms? Cryptographers, when they design algorithms, do so generically, that is, without a specific application in mind. Well, really, they do have applications in mind, but they try to make their algorithms good for many applications. They recognize that the computing industry at large operates over the two main models, so they try to define algorithms that will be "performant" (fast, light, economical...) in either or both.
For a software-based algorithm, this means using the operations that are natively offered by CPU. An example of a software-based algorithm is the hash function SHA-256, which uses a lot of 32-bit integer additions.
An hardware-based algorithm will rather concentrate on operations that yield better dedicated circuits. The new SHA-3 function (aka "Keccak") is of that kind: it is built around bitwise logical combinations. For a CPU, a 32-bit ADD and a 32-bit XOR have the same cost: both are elementary operations that will be executed in the same time, with the same CPU resources. But when you go hardware, the two operations are quite different: the ADD requires many more transistors (because of the carry propagation) with a deeper circuit (again because of the carry propagation), so the XOR is cheaper (less transistors, so less silicon area), lighter in energy consumption, and faster (because of the shallower circuit). The consequence is that Keccak tends to be a hog in software but a screamer in hardware.
Of course, the full situation is complicated. There are many types of CPU, some of them (the GPU) being optimized for tasks that general-purpose CPU are traditionally bad at (in particular heavy parallelism). Some modern CPU now include circuits dedicated to some specific cryptographic algorithms (e.g. for AES encryption). Also, FPGA have some, let's say, inclinations toward CPU, in that they are reprogrammable, and some include CPU-like features (RAM blocks, or even embedded DSP/microcontrollers). This blurs the limits.
In fact, the notion of an algorithm being "for software" or "for hardware" must be understood as a broad design categorisation that describes more the initial intent of the cryptographer who produced the algorithm, than a cleanly defined, mathematical property. There are extreme cases, e.g. the former AES candidate RC6, which is purely software (it uses an integer multiplication, a very expensive operation in hardware, that just happens to be part of the panoply of most CPU because it is a very useful operation in many cases), and the old GSM phone encryption algorithm A5/1, which is extraordinarily efficient in hardware (can be done in less than 500 gates) and remarkably slow and cumbersome in software.
Most modern cryptographic designs try to be versatile, and while they are usually meant to be more software-friendly or more hardware-friendly, it is considered a good thing if they do not yield abysmal performance in either case. This is one of the reasons, maybe perhaps the main one, that made Rijndael the winner of the AES competition: while not extraordinarily performant on, say, a big PC, it was still decent on all envisioned software platforms and in dedicated hardware; ultimately, this allowed the inclusion of such dedicated hardware in modern lines of CPU.
An exception is password hashing functions, that purposely aim at being most efficient on the defender's platform (supposed to be a general-purpose PC, i.e. the epitome of software), and as slow and expensive as possible on dedicated hardware. The recent Password Hashing Competition revealed a number of candidates that try to achieve this goal either with extensive usage of RAM (a traditionally sore point in FPGA), or with heavy usage of multiplication (as in Makwa).
