Create a leaf
 

How would one go on creating a leaf for like....a palm tree?

I'd think paint effects would be the method of choice unless you are looking for something with extreme detail as used for a closeup.
In which case I'd say box modeling would probably work just fine with a smooth, or convert to sub-ds.

It really depends on what extent you wish to take the details.

A better and more realish method would be a polygon plane and 1 and 1 in divisions. Find a good resolution image of a palm leaf and apply the textures. Ensure that the texture as an alpha channel.