Do all wires on basement walls have to be in conduit?
2005 NEC
ARTICLE 334 Nonmetallic-Sheathed Cable: Types NM, NMC,
and NMS
334.15 Exposed Work.
(C) In Unfinished Basements.
Where cable is run
at angles with joists in unfinished basements, it shall be permissible
to secure cables not smaller than two 6 AWG or three 8 AWG conductors
directly to the lower edges of the joists. Smaller cables shall be run
either through bored holes in joists or on running boards. NM cable
used on a wall of an unfinished basement shall be permitted to be
installed in a listed conduit or tubing.

So basically if the cable is on the ceiling, it does not require conduit. If the cable is run along walls, it requires some form of protection. This protection can be conduit, or some other form of protection. You could use a scrap piece of 2x4, for example. Simply attach the 2x4 to the joist, and then attach the cable and box to the 2x4 (following proper NEC procedures of course).
When running cables on the ceiling, only 6/2 and 8/3 (and larger) NM cable can be run along the bottom of joists (perpendicular to joists). Smaller cable must run through bored holes (following 2005 NEC 300.4), or along running boards (boards that run perpendicular to joists e.g. main support beams). When installing cable on the ceiling that runs parallel to the joists, you can attach the cable to the face of the joist (as per NEC 300.4(D)).
As always, check your local codes before installing cable as your location may not follow NEC 2005.