Step 1 - Scribble fun
Make a new document, any size you want. I'm using 200x200 for this time. Start off by making a layer, and just plain scribbling randomly at it to make a random sketch.
Step 2 - Filters
Go to Filter»Pixelate»Fragment. Click OK once the menu shows up. Now you have a distorted shape.
Step 3 - Sharpening the Texture
Now we'll kick the brush up a bit and sharpen it up. Go to Filter»Sharpen»Sharpen to sharpen this distorted sketch up a bit more.
Step 4 - Defining the Preset
Delete the bottom layer by right clicking it on the Layers Window, and hitting delete layer. Now go to Edit»Define Brush Preset. Give your brush a name if you want, and hit OK. Now when you select your brush, look for your newly made brush. Enjoy it, and mess around with it to try and get something that appeals to you.
End! Job well done! :)