I can't tell if I would need to start by creating a physical paper cutout or if I could do it completely in Photoshop. I am not sure how to approach this, so any suggestions of tutorials or Youtube videos would be a great help.
I commented, but this actually is starting to look like an actual paper design ( see: http://smadani.com/ArcticPaper%20page.htm ) and that person's portfolio includes a book "Paper Engineering; 3D Design Techniques for a 2D Material," Rotovision, 2009.
The portfolio page linked above has other images which where the items look more like stacks of paper. Were I to do this in my garage, I might have a die made for 100$ and then use a press or even a car jack and some plywood sheets to punch out the letters from a ream or stack of paper. For thinner items, just an exacto knife.
As far as faking it:
Photoshop, some drop shadows, black stencils with color overlay, layer fill set to low, and a double layer of text with slightly different color overlays and shadow settings (one layer offset vertically a few pixels.) A 3D app is still the best option, since it will be way more realistic. The devil is in the details in a piece like this.
This is 3d render. If you want to do simmilar image in PS you will need to use shadows and gradient (white-black with multiply or screen blending). Lights and shadows must be coherent. It will be like painting - artist always sets two or three sources of light. For such pictures basic knowledge of using light in photogrphy is also usefull.
You can usually write text in these softwares (it's really easy in Blender) and extrude them to have 3 dimensions. Then you apply a texture (white or maybe light grey in this case, experiment) and find/create some leaf models to place around it with the same texture.
Afther this you will place some light sources (probably two) and set the settings for the light source.
Then you place the camera where you want it (using an image preview window) and then when you're happy you can start the render process.
After this you might want to import the image into Photoshop to touch up some parts, but this is generally the steps to produce something like this.
I can't give more info as I don't know which software you'd decide to use.
If you've never used 3D software before, I'd suggest using Blender. It has an easy learning curve and can produce professional grade renders for free.
Hope it helps some :)