For a 3×3×3 cube there are three different conditions to check, usually decomposed as "permutation parity", "edge parity", and "corner parity".
(Mathematically, the group that the describes all ways to take apart and reassemble the cube has the group of legal movements as a normal subgroup, and the quotient group is $C_2\times C_2\times C_3$, so it is natural to group the check into three parts. In principle there ought to be equivalent ways to deal with the $C_2\times C_2$ factor, but the overall and edge parities are so natural that looking for the other decompositions doesn't seem worth the trouble).
We imagine that the spindle axes (and therefore the center cubies) stay fixed in space -- turning the entire cube is trivial and ignorable.
Permutation parity: This rejects 1/2 of all configurations. In this step, ignore which way each of the little cubies is turned and just look at where it has ended up. In this way each way to assemble the cube corresponds to some particular permutation of the 20 non-center cubies. Each legal permutation is an even permutation (because each quarter turn is a product of two 4-cycles and therefore itself even). On the other hand it is well known that any even permutation can be achieved, as long as it doesn't try to interchange edges with corners.
To check whether a given permutation is even, just write down the permutation (i.e. the function from "where the cubie is" to "where it ought to be") and compute its sign by any standard methods -- e.g., by counting inversions or unraveling its cycle structure.
For edge and corner parity, we temporarily forget the difference between opposing colors on the cube -- say, we call both of white and yellow $X$, both of green and blue $Y$ and both of red and orange $Z$.
Corner parity: This rejects 2/3 of all configurations, and can be defined in the following way: Since we have unified opposing colors, each corner has the colors $X$, $Y$ and $Z$. Let's say that a corner is "oriented correctly" for its instant position if its $X$ side is next to an $X$ center. (This treats the $X$ color pair specially; the $Y$ and $Z$ sides may or may not line up with matching centers). Now for any way to assemble the cube, consider how many clockwise 120° twists of a corner-in-place it would take to orient all of the corners "correctly" without moving them. If this number is a multiple of $3$, the configuration passes the corner parity test. (It is easy to see that a quarter turn of an $X$ face keeps this number unchanged, and only slightly more complex that a quarter turn of $Y$ or $Z$ changes it by a multiple of $3$).
Edge parity: This rejects 1/2 of all configurations. It can be computed much in the same way as the corner parity, except that the definition of "correct orientation" for an edge is a bit more involved. One may take, for example:
An edge with a $X$ side is oriented correctly if the $X$ side is next to an $X$ center or if the edge is in the middle layer and would become correctly oriented by a quarter turn of the $Y$ (but not $Z$) face it is in.
A $YZ$ edge is oriented correctly either if it sits between a $Y$ and a $Z$ center in the obviously matching way, or if its $Z$ side is next to an $X$ center.
One may now check that a quarter turn of an $X$ or $Y$ face doesn't change whether any edge is oriented correctly or not, whereas a $Z$ quarter-turn changes each of the four edges it moves from correct to non-correct or vice versa. Thus, every legal move changes the number of correctly oriented edges by an even amount. So we must reject any way to assemble the cube that ends up with an odd number of incorrectly oriented edges.
Though not immediately obvious, these three tests will reject any configuration that cannot be solved.
The corner-parity check carries over to larger cubes unchanged, but the two other tests cannot always be directly applied to larger cubes. For a 4×4×4 cube with indistinguishable center pieces, the corner parity check is the only check; anything that satisfies it can be solved. For a 5×5×5 cube, the virtual 3×3×3 formed by corners, middle centers and middle edges must be solvable according to the 3×3×3 rules, and it turns out that the remaining pieces can always be solved, again assuming that centers are indistinguishable. I think that larger-yet cubes continue the pattern from 4×4×4 and 5×5×5.
There are special parity checks to apply for supercubes (where the orientation and/or permutation of center pieces of the same main color matters); I don't remember offhand how they work.