The safest thing when starting out is to keep anything valuable on you when you log out.
For keeping stuff you can't carry safe, the first option is to build a leanto, which can hold two liftable items. You can only own one leanto at a time, but for the early game sticking two crates in it can give you a little secure storage. People can still steal your stuff, but it's a crime so they need the Theft skill, which raises the bar slightly.
http://ringofbrodgar.com/wiki/LeantoThe next step is to build a personal claim. This will protect anything on it from being stolen by making it Theft to do so. People can still do it, but it's a little less likely and not totally painless for them. Even better, you can build a roundpole fence on your claim. To break through the fence requires the Vandalism skill, which is much more expensive than Theft. Also, you can build gates in your fence and anyone entering through a gate won't be able to commit crimes, so it's perfectly safe to just leave your gates open.
http://ringofbrodgar.com/wiki/Personal_ClaimThe final step in the early game is to build a palisade, as you seem to be aware.