This is a question of experience and training.
They use "advanced" programs like Gimp or Photoshop. If you use Paint, you won't be able to make these kind of textures ; the program itself is really basic and does not allow you to make advanced effects like gradients and everything.
There's also the question of experience. They must be using these programs for a long time now and made many heads before having acquired this level of skill.
I suggest you to download Gimp and practice on it. You should find tutorials about the basics, and then progress within the time.
Good luck with that.
PS: If you already have Photoshop, then use it instead of downloading Gimp.