First look at a new integrated workshop that makes it easier to create and upload skins, and lots more.
Click on "Workshop". In the workshop, click on "New" to make a new item:
Then select the type of item you want to make from the dropdown: 
Then click the "Edit" tab and click the download button to download the default diffuse texture:
Then draw all over it in Paint, Photoshop, or whatever open source crap you have installed:
Click the folder button to update the texture to use the new one: 
And blammo. 
If you keep editing the texture, it will automatically update in game. Clicking "Publish" generates an icon and uploads it to the Steam Workshop for everyone to see.
This is available right now on the prerelease branch, though it's still a heavy work in progress. The Rust Workshop has a project page with an almost empty wiki here. If you're finding something particularly hard to do, or having trouble converting your existing items please let me know via twitter.