First of all, welcome to the forum! ... and now on to some clarification

To be eligible as a member of Family class (partner-sponsored visa, as you call it), you and your girlfriend would have to be either married or common-law partners, and for that you need to prove at least 1 year of continuous cohabitation (joint lease agreement, utility bills in both names or bills coming to both of your names at the same address - but a notarized statement from your landlord would also be acceptable). However, it has to be for 12 consecutive months, and even if you were travelling during that time your "base" still has to be together somewhere.
At the moment you don't seem to meet this condition, but I'll try and answer the rest of your question anyway just in case

But how do they tell when the pictures are from anyway? How do I prove that a picture was from a specific time?
You can't, but this is why it's important to include a wide array of pictures covering different events and occasions (different clothing, different hair, obviously different locations, with different people... anything that would indicate a certain time span. This is also why holiday pictures are very useful; if there's a big Christmas tree behind you and you're both opening presents, it's easy to tell when this is happening and it isn't very likely you just staged it for a photoshoot

)
Are personal referees okay evidence? Can a friend confirm that we started seeing each other in January 2010? Can Landlords? Can anyone?
They can, as can family members from both sides. Have them write letters, ideally notarized and with their contact information, describing the development of your relationship from their point of view.
I read that chat logs can be used as evidence, but this seems like an odd and awkward thing to share with someone.
Ah, yes, well

I didn't mind sharing with the world, but my husband was objecting on that grounds as well - we ended up sending a few samples covering different events over some time, and printscreens showing the /number/ of emails in our inboxes and MSN log folders we had saved. Hopefully it went to show we were constantly in touch without letting the CIC officers in on inappropriate details ^^
As for Federal skilled worker application, I have no idea -_- But it would be awesomely terrific if you could pull that one off, mostly because it's simpler and much more straightforward than Family class... although it would still take quite some time.
The way I see it is we have few options! 1. I get a sponsored visa for Canada 2. I convince her to stay in NZ on a partner visa (much easier than a canadian one!) or 3. I fly to Canada and live with her on a visiter visa until we have aquired enough evidence to get a spouse visa!
Option 1 is not available to you at the moment, as you aren't married and don't meet the 12-month condition for common-law. So, you can either try getting into Canada on your own merit (through FSW application or on a work visa if someone would get a Labour market opinion for you), or you can try meeting the common-law condition. However, in my very unprofessional opinion, that would have to start from June 15th, as the time you spent together before that and travelling back and forth doesn't count as "continuous cohabitation".
Now, this business of living together can be either in New Zealand if she's willing to stay, or you could come to Canada as a visitor (you would be able to extend your status from the initial 6 months once you are in Canada; "preparing a family class common-law application" usually goes well as a reason for extension

), but during that time you wouldn't be able to work unless you had an (unrelated) work visa.
Or you could get married and speed things up a bit

As for the type of evidence you would need to mix in with the ones you already have, I would try opening a joint bank account, put each other on some insurance/will stuffz, get both names on bills and such, anything in the financial/combined affairs department really. I warmly recommend you go through the processing manual:
http://www.cic.gc.ca/english/resources/manuals/op/op02-eng.pdfAnd best of luck
