I just want to add that although you will apply the edges rule of thumb, not EVERY edge that has attached UVs has to be soft and vice versa. As depending on the look your going for some edges may just need to be hard even if the UVs are connected. It does help though, especially with eliminating seams. I use Maya and found a script that harden only the border edges of my UV shells, the first article link here does an exceptional job of explaining the benefits of hard edges and also provides methods for Maya and Max on how to easily harden your UV shells border edges. The second article goes over something that many may overlook, you simply cannot go too low on polys. Adding some of those same support edge loops on certain areas of the low poly can do wonders. As the high poly detail is being baked on top, if your getting unwanted gradients or falloffs in a certain area you may also want to check that the high poly has enough support loops on that area of the mesh.
A cage shouldn't be necessary and I think painter is one of the first programs that's exceptional at providing a cageless baking method. I can 100% attest to this. Some steps in this method were taught to my friend Chris Chowell by an instructor that was teaching substance painter. I was using a cage prior to this and I feel there's no comparison and the results will show. I would definitely try this method first as I now feel cages are a waste of time after using this method.
1)Your high and low poly must be aligned/centered in your scene and you should always reset xform on both,
2)For Match By Mesh Name to work:your high and low poly must have the SAME name except you append _low to the low poly and _high to the high poly. You MUST apply the suffix to the high and low poly, the Match:By mesh name- option in the baker will show this as well.
3) I normally don't triangulate but doing so is generally recommended. I export low poly with smoothing groups and high poly with smoothing enabled(and I'm going off my settings used in Maya so whatever the Max equivalents are).
4) When baking in painter I leave max frontal at default and set max rear to 0.7, set Match to By Mesh Name and Anti Aliasing to 4x4 or 8x8 and bake normal, world space normal, curvature, and position/thickness. Then I bake the AO separately with AA set to 4x4.
And here's what's even better, You can have your high/low poly meshes in multiple sub parts and apply the aforementioned naming convention to each sub part then just group the sub parts and export them as a single mesh group. When you bake in painter using Match by Mesh Name, painter will match each individual sub part which can give even more accurate results. I also added a 3rd link which I found the other 2 links from. It's a great source that provides a ton of info on normal mapping, it helped me a lot with mesh preparation in order to achieve better bakes.
http://polycount.com/discussion/107196/youre-making-me-hard-making-sense-of-hard-edges-uvs-normal-maps-and-vertex-countshttp://polycount.com/discussion/147227/skew-you-buddy-making-sense-of-skewed-normal-map-detailshttp://wiki.polycount.com/wiki/Normal_map