~~~~~THIS BUILD IS A WORK IN PROGRESS. I AM STILL TESTING AND UPDATING~~~~

Pros
Assassin
Innate Lifesteal
Good Jungling
Good Farming
Excellent Ganking/Chasing
Good Harass
Spellblock skill

Cons
Squishy
Ultimate can be tricky to use

My Concept:
Because I was frequently getting focused in team fights, I decided a tankier build was needed, much like Irelia. Therefore, my build attempts to stack HP/armor/MR while still maintaining some damage.

NOTE: My runes/masteries are NOT necessarily the best runes to use with Nocturne, they are simply the ones I am using at present. Testing and updating soon.

I currently use the following runes (Other suggested runes are in parentheses):
Marks - Armor Pen
Seals - Dodge (Armor, MP5 or MP5/lvl, AD)
Glyphs - CDR (AtkSpd, CDR/lvl, MP5)
Quints - Flat HP (Armor Pen, AtkSpd)

Again, these aren't necessarily the best runes, just the ones I'm currently messing around with.

I usually build Nocturne as 21/9/0. Pretty self explanatory:

-21 into Offense for extra attack speed, cooldown reduction, and anything else that can boost my damage output.
-9 into Defense for the extra dodge and Nimbleness mastery, which further utilizes my dodge runes and allows my dodges to give even better chasing ability with the Nimbleness speed boosts.

It's worth noting that I'm also experimenting with building 9/21/0. I usually have pretty good success with this build, as it allows me even more survivability.

I personally like Ghost/Smite. Smite is necessary for jungling, and Ghost gives me additional chasing power and makes for easier get-aways.

Other options:
Clairvoyance - Excellent choice on Nocturne for those slippery champs that JUST barely make it into the bushes or out of sight range when you ulti.
Flash - Good for escaping, but I find Ghost to work almost as well, and Ghost makes for easier chasing.
Ignite - A bit of extra damage, but I find that it usually makes little difference in combat with Nocturne since this build is kind of tanky anyway and most of my damage comes from chasing/sticking with the target.

Put a point in W at level 1 for the attack speed increase, then focus on leveling your Q, putting points in your E whenever you can't put them into your R or Q.

I.E. R>Q>E>W

Your early game Skill Sequence should be: W Q Q E Q R

Your main damage dealing combo:

Paranoia --> Paranoia Teleport --> [Duskbringer --> Unspeakable Horror], AKA: R R Q [E Q]
Rinse and repeat the brackets (E Q) till opponent is dead. =D

Note: Don't use your R to engage if you don't have to! If you can, just open with Duskbringer (Q)! This allows you to save your ultimate for if they manage to escape, so you can teleport straight to them and finish them!

I usually jungle Nocturne, so I start with Cloth Armor + 4 HP Pots. I build into Wriggles Lantern and get my boots (I like either Mercury's Treads or Berserker Greaves, depending on how much CC I'm going up against). One reason I like Wriggle's is that it allows me to place wards either on dragon or their buffs.

Nifty trick: Put a ward on their red or blue buff, then when they next go to get it, use your ult to teleport to them for a quick and easy kill.

Next I pick up Heart of Gold for some more HP and immediately start building my Youmuu's Ghostblade. The items up to this point usually give me enough HP/Damage to get up to my BF Sword and build into Bloodthirster.

Next I build Frozen Mallet for the big HP boost and the slow (No one will escape you now...=D), and an Atmas, which gives some more armor and increases your damage considerably since it gives a damage increase based on your HP (which should be pretty beefy right about now).

Now you get some choices. I typically build my HoG into a Randuins, then grab a Banshee's Veil (if they have a lot of AP), Infinity Edge (if I'm not getting focused and want to get some extra damage in), or Black Cleaver (if they're stacking armor). You can also skip the Randuins and sell your HoG for one of the latter items as well, depending on the team you're up against.

Good luck, and good ganking!

My Jungle Rotation:

Start at Blue Golem (Have mid and top lane help you bring it down to half hp, be sure to pot as soon as you take damage). From there out, it's pretty standard:

Blue Golem --> Wolves --> Wraiths --> Golems --> [Back] --> Wolves --> Wraiths --> Golems --> Red Lizard