This post is for 3.1.X but the process should be the same for 4.X.
Take a packet capture of the traffic you want an App-ID signature for. This example is a flash video over HTTP.
(Screenshot shows a different set of headers than the example below is based on)
Look in the capture for fields in the headers that should be static no matter what browser or operating system the client is using and pick those to make a signature with.
Go to the Objects Tab > Applications then click on New...
Create a name, set the properties and characteristics.
Go to the Signatures Tab and click New...
Set a name for the Signature.
Create an And and an Or for each item you want to match on (each item to match on must be at least 7 bytes long or roughly 7 characters)
In this example I'll use http-req-params and http-req-host-header. These will match the GET and Host lines in the header send from the client to the server, looking for these values.
Remember to escape periods with a forward slash.
I don't remember where I found this, but it's very helpful:
Field/context definition for custom App and Threat Signatures
Edit: Here's a much nicer guide Palo Alto made for 5.X