It works like binary, except: after the rightmost 3 columns (least significant digits) being 2^0 (1), 2^1 (2), 2^2 (4) (from the right to left), then each column further left is worth 3 additional powers of 2, rather than just being worth one additional power of 2.
So in binary, the 4th column from the right is the 8s column, but here the 4th column from the right is the 32s column because you jump 3 exponents to 2^5 (32). Then the 5th is 2^8 (256), the 6th is 2^11 (2048), and the 7th is 2^14 (16384).
And instead of being strictly limited to a max digit of n-1 like in a base system, you just fill up the columns as much as possible from most significant to least significant digit.
So even though the example showed a 6 as the highest possible digit, there could be a 7 in some numbers in this system, anywhere except in the final 2 digits. (e.g. take our number 31, it would need 7 in the 4 column, then 1 in the 2 column, and 1 in the 1 column.
Update: To address the comment by JLee, yes, you still actually have a unique mapping of Earth numbers to Mars numbers, assuming Martians intuitively follow digit restrictions that are natural to their number system, which they would.
It would just be obvious to them that you can only put a 1 in the ones and twos columns, but then up to a 7 in the higher columns. Note that the columns go on forever to the left, always being worth a factor of 8 more than the previous, so you can always get enough digits to get high enough to represent all numbers. Just like in our system every column is worth an additional factor of 10, and you keep going left to get numbers as big as you need.
Here is a simpler way of me summing up how the number system works.
They use a hybrid of binary and base-8. The rightmost 2 (least significant) digits are in binary, and after counting to 4, their number columns are in base-8. Basically if you chop off the right 2 digits, you have an octal representation of counting "groups of 4", and then the right 2 digits tell you whether to add 0,1,2, or 3 to that.
You could imagine such a system evolving from a Roman-Numerals like system where they used sticks to count as high as 3, but above that they used a letter to represent 4 sticks, and then another letter to represent 8 of the first letter (which represents 4 sticks), etc.
The way I did it:
After being a bit distracted by the fact that the Earth numbers were made from breaking up 1234567890, I focused on the smallest number which also happened to be simpler, with 2 zeros and just looking at 3 and 12. Well 3x4=12, is it possible that the third column could represent 4? Hey, that's like binary, but you'd never put a 3 in binary. Let's see if it's an irregular number system that still works on the "columns" idea.
I scanned the whole list and noticed that if the Martian number ended in 1 it was odd, else it was even. This is also like binary, and implies that the right column is the ones column. That means the 2nd column is probably a twos column, but I should check that it's not weird, like threes. It can't logically be anything else, since we already are thinking the 3rd column is fours (unless we are way off base).
So then I moved up to the next smallest number: 123. I played with it, subtracting the amounts if I was right about the ones, twos, and fours columns, and happily found that the remainder was divisible by 3, and the result was 32, so this must be the thirty-twos column, which is still a nice number in binary-land.
I then went on to 345 and 456 and confirmed that if the fifth column was 256, then both of these numbers worked out, and saw the pattern and then attacked the largest number to be sure it was always jumping by 2^3 per column.