-You MUST complete the normal game on NORMAL OR HARD. Completing it on easy will NOT unlock New Game Plus.
-You start at the beginning again and have to play through the story once more. You can skip cut scenes by double tapping B.
-All your solved riddles will carry over between the two game modes (Yes, this means you can go back to regular to hunt puzzles if you want) Any discovered map markers also stay.
-Side Missions DO NOT carry over, you only need to do them if you plan on going for Perfect Knight 2.0 As it is required you complete them in both modes.
-You keep all of your upgrades and gadgets. If you try to use some gadgets too early or at a wrong point in time Batman will say "there's no time for this" and won't let you use it.

-Enemies attack faster and there is no attack indicator. Pay close attention to their animations. There's no fault in spamming the counter button if you think multiple enemies are attacking, just don't lose your combo.
-Many more enemies are now also using knives, shields and body armor. My strategy for this was to build my combo off the regular dudes (Knowing how to effectively counter and time critical strikes is CRUCIAL). And then use my instant takedown on the well-armed guys. Using the "Destroy Equipment" takedown is also effective if you want to take that item out of the fight permanently, but this will cause no damage to the baddie holding the item.
-Otherwise, be defensive if you are getting low health and double tap A away if you are in a tight spot.

-Enemies will have proxy mines and body armor early in the game, and there will almost always be a jammer.
-Armored guys MUST be taken down with gadgets and/or a loud takedown. Use the sonic boomerang explosion (Upgrade) on either an armored guy, or the jammer (Remember you can only do this once per scenario.)
-Using the fully upgraded disruptor on mines when an enemy is near them is a great way to instantly take them down without giving your position away (you can only do this twice per scenario).

-Bosses will have more health and may have slightly altered mechanics. All of them are relatively simple if you learned their mechanics from normal, except for Mr. Freeze which I discuss below.

-Freeze will shoot you with his beam if you are in his front vision in line of sight, DO NOT GET HIT BY THIS.
-If Freeze knows where you are but can't hit you, he will lob freeze grenades over obstacles in attempt to hit you.
-If Freeze has seen you recently, he will head to your last known position and attempt to track your footprints. You can end your footprint "trail" by jumping off ledges or using the line launcher. This can be used to your advantage by putting your footprints in certain positions and using a takedown.
-If Freeze has no footprints to track and doesn't see you he will send out 3 drones. These drones take about 10 seconds to lock onto you and will shoot straight at your position when you see their beam turn red and hear a distinct sound. Freeze will now head straight towards that position, and then track your footprints. You can use this to your advantage to set up takedowns.
-As you probably know from normal, each time you use a unique takedown, Freeze will activate some sort of countermeasure or freeze certain objects so you can't do it again.

Here's whats important about the New Game Plus version of Freeze:

-You no longer have information on what Mr. Freeze is doing, though its pretty easy to see what he's doing by the animation he is performing.
-Using your Bat Cowl (AKA Detective Vision) will cause a "meter" on the right side to increase. The meter will start turning red if you use it to long, and Mr. Freeze will eventually send out a jamming signal (permanently, I think) if you let the meter fill up. Only use Detective Vision for short periods of time to avoid this.
-You must perform 10 takedowns from the list below to beat Mr. Freeze.


Here are the ways you can takedown Freeze, get some punching in and lower his health.

Easy

-Shoot one of the 2 Magnets in the room with a negative charge. You can do this right at the beginning of the fight. Be quick to avoid taking damage.

-Stealth takedown. This one is easy, you just need to get behind Freeze.

-Floor vent takedown. He will see you in the vents if he is looking down at your footprints.

-Use the disruptor on his gun. I'm not sure if you need the regular or the upgraded version of the disruptor, as I had every single upgrade at the time.

Difficult

-Use explosive gel to blow a structurally weak wall towards him. The gel has a proximity effect which tells you when he is in damage range of this, so I recommend you plant this early in the fight and use it when you need it.

-Electrify the live wire in a pool of water, 1 of 2 buttons can be pressed to accomplish this.

-Ledge takedown. For some reason the "Takedown" notification didn't pop up in my version of the game and the take down won't work close to the ramp. Batman also seems to automatically climb up the ledge if you use RB to get up there. So start ON the ledge and press RT + A instead.

-Drop Attack. Jump off one of the consoles on the second floor of the room when Freeze is directly below you on the first floor. Be aware that Freeze will ice over the consoles after this, you will not be able to climb up them afterwards.

-Fall through the glass ceiling on top of Freeze. There are 1 of these on either side of the room. Wait for the "Takedown" notification to appear, you need to be directly above him.

-Takedown through a glass window. Freeze needs to be relatively close for this. Watch for the "Takedown" notification.

-Glide Kick. This one is tricky since getting height in this room is difficult, but it can be done. A good method of doing this is to tightrope walk on your Line Launcher (requires upgrade). Note that after you do this, Freeze will flood the room with mist, not only obscuring your normal vision, but also icing over your cape, meaning you can't glide anymore.

-Kick Freeze in the side or behind while on the line launcher. I had the most difficulty with this one. You have to be PERFECTLY aligned with him, so start on exactly the same level at him and TAKE YOUR TIME TO AIM. If you try to do this while Freeze sees you, you will take an enormous amount of damage and the takedown will fail. After doing this Freeze will immediately see you whenever you use the line launcher from the sound it makes. [Now that I know that there is more takedowns than the number it takes to kill him, I would recommend skipping this one.]