AFTER:
-Replace wall switch with a new dimmer switch going to some new recessed lights I'll be installing.
-Hardwire the outlet as "always on" so that a switch no longer controls it

QUESTION:
1. How do I get from "BEFORE" to "AFTER"?

Is this along the right idea?
->Incoming B/W/G. Tie BW together to make outlet "always on", right?
->How can I power my new dimmer switch if I want the outlet "always on" though? Do I just run a short black wire from the "B/W" that I just tied together? If yes, then what do I do with the "W" coming from my recessed light....?

Basically, I need a power supply to tap from, can't that be the wire that is currently connected to my wall switch?

If you want the switched half of the receptacle to stay on, you can just wire nut the black and white together. If it you do that might not be a bad idea to get a black Sharpie and color the last couple of inches of the white wire so that in the future whomever goes in that box knows what's going on. Pull the switch and tuck the wires neatly in the back of the box.

The other option involves understanding what happens when you switch one half of a receptacle. There is a little brass tab that connects the two screws. That tab is broken off and then the receptacle is wired. The easiest thing to do is simply replace the switched receptacle with a new one, leaving the wires that go to the switch disconnected, capped, and tucked neatly in the back of the box. The other option would be to use some short pieces of wire to kind of "jump" to the now switched side of the receptacle.

What you didn't say, is how you are planning on powering these new, recessed cans. One option might be to use the existing cable running from the switched receptacle to the switch to bring power to that box and then on to the new cans. Let us know your thoughts and we can take it from there.

Be basically said what I think you are saying which is:
-->Let's call the existing wire going from the receptacle to the switch "EXISTING"
-Disconnect EXISTING from switch & get rid of the switch
-Disconnect EXISTING from receptacle
-Jump wire on receptacle (thus "always on" is achieved)
-Reconnect EXISTING black to one bottom screw on receptacle and EXISTING white to other bottom screw on receptacle, thus giving me tapped power from the receptacle and changing EXISTING into a black & white (& ground) power wire
-Connect EXISTING black to black on new dimmer (and ground to switch box)
-Run new wire from 2nd black on dimmer to recessed lighting
-Connect new wire "white" to EXISTING white (as well as new wire "ground" to EXISTING ground on switch box)

That should take care of it all, right?

If the boxes are metal, you'll want to ground those was well as the devices.

I just opened the outlet. Both brass tabs are intact, 2 incoming Romex wires, nothing else.

Single black from Romex1 going to top outlet brass screw and single white from Romex2 going to top outlet white screw. Outlet & box are grounded via both wires.

Remaining white from Romex1 and remaining black from Romex2 are wire-nutted together.

Nothing is coded black.

Is this how I proceed? (Power will be off at circuit breaker during everything except testing)
1. Disconnect all wires. Through trial & error, connect black to brass, white to white from one of the romex wires to outlet and see if that provides power to outlet, that will be the incoming power romex (and not the one going to the switch).

2. Keep POWER romex connected to brass/white screws on outlet. Connect NON-POWER romex to bottom brass/white screws. Keep all grounds grounded as they were previously (with outlet & wall box both grounded via green screw on outlet and green clip on wall box).

3. No pigtailing is necessary. No coding of wires is necessary.

-->The above steps should now have the outlet "always on" via the top 2 terminals and I should have outgoing power now to my new dimmer switch via the EXISTING (or NON-POWER which I just turned into a POWER) romex.

This all correct?

Romex 2 is what's bringing the power in. Romex1 takes the power to the switch (and back). As for your plan, it's fine. As I said, I prefer not to wire through devices but there's nothing that says you can't.

Mike - Why do you prefer not to wire through devices? Just curious, and thanks for clarifying that technically, I CAN do it.