The anticommutation rules for creation/annihilation fermionic operators are what defines these operators. The "proof" that they are correct is that they produce a theory that is compatible with the antisymmetric nature of fermions (and with all the other experimental results of course). For example you can check that they produce the expected result for average values of one particle operators, with the minus signs expected for fermions states (see for example the second section of this other Phys.SE answerthis other Phys.SE answer).
About the particular calculation you refer to: the problem is in the way you "neglect" the order of the creation operators defining your initial state. Starting from the definition of the state $|a,\dots,\sim \! b\rangle$ in terms of creation operators: $$ \tag 1 |a,\dots,\sim \! b\rangle = c_a^\dagger |\sim \! a,\dots,\sim \! b\rangle, $$ you have, using $\{ a^\dagger,b^\dagger \} = 0$, the following: $$ \tag 2 c_a c_b^\dagger| a,\dots,\sim \! b \rangle = c_a c_b^\dagger c_a^\dagger |\sim \! a,\dots,\sim \! b\rangle = - c_a c_a^\dagger c_b^\dagger |\sim \! a,\dots,\sim \! b\rangle \\= -c_ac_a^\dagger |\sim \!a,\dots,b\rangle = - |\sim \!a,\dots,b\rangle. $$ On the other hand, you have $$ \tag 3 c_b^\dagger c_a | a,\dots,\sim \! b \rangle = c_b^\dagger c_a c_a^\dagger | \sim \!a,\dots,\sim \! b \rangle = c_b^\dagger | \sim \!a,\dots,\sim \! b \rangle = | \sim \! a, \dots, b \rangle. $$
This is compatible with the (anti)commutation rules, as you can see summing (2) and (3), and remembering that for $a \neq b$ you have $\{ c_a,c_b^\dagger \} = 0$. The case $a=b$ is also easily verified, but your notation seem to implicitly assume $a \neq b$ so I wan't address it here.