As stated, any number is divisible by 3 when the sum of its digits add to a number divisible by 3. This means adding a 3 or a 9 in any position in a number will not change whether it is divisible by 3.
The next insight is that 5+1 = 6 and 1+8 = 9, both of which are divisible by 3, but 5+8 is not divisible by 3. Let's begin by finding the 4 digit numbers. We know that the digits must either contain 3,9,1 and 5 or 3,9, 1 and 8. This gives us 2 combinations, each must contain a 3 or a 1 with the starting digit. This means there are 2*2*3! ways of arranging those numbers.
Now for a 3 digit number. We know this number can't include 3 AND 9, since then no matter what the last digit is, the number will not be divisible by 3. A similar argument shows we can't have 3 nor 9 in the number. Therefore, we must have 3 OR 9 in the number. This means that there are in total 4 combinations of digits - 1,5,3 + 1,6,9 + 1,5,9 + 1,6,3. 3! ways to get a combination of them means there are 4*3! 3 digit numbers.
Then 2 digit numbers. Obviously, our combinations are 1,5 + 1,8 + 3,9 which means we have 2*3 combinations.
There are finally only 2 1 digit combinations. Therefore the total number is:
2*2*3! + 4*3! + 2*3 + 2