Solution 1:

Dictionary Views of 'dinkum' and 'fair dinkum'

Eric Partridge, A Dictionary of Slang and Unconventional English, eighth edition (1984) has these entries for dinkum as a noun and as an adjective:

dinkum, occ[asionally] dincum, n. Work, toil: Aus.: 1888, Boldrewood, 'An hour's hard dinkum'; ob. Ex Derbyshire and Lincolnshire dial.; cognate with Gloucestershire ding, to work hard: i.e. dincum, -kum, is prob. a perversion of dinging, with which cf. dink, to throw, toss, a var. of S.E. ding, to strike. ([Joseph Wright,] E[nglish] D[ialect] D[ictionary].) ...

dinkum, adj. (Often fair dinkum, occ. square dinkum.) Honest, true, genuine; thorough, complete: Aus.: prob. sinc ca. 1890. S.B. Lancaster, Jim of the Ranges, 1940, '"Straight dinkum?" It was the old touchword of their boyhood.' Wilkes's first citation is 1894. 'Are you fair dinkum?' = Are you telling me the truth? (Culotta). Perhaps ex dinky, adj. q.v.; but actually dinkum prob. derives ex fair dinkum, for in Lincolnshire dial. we find fair dinkum, fair play, before 1898; the EDD derives it ex Lincolnshire dinkum, an equitable share of work.

And Kel Richards, The Story of Australian English (2015) has this:

DINKUM a word used by miners in Derbyshire to mean 'work' (especially hard work). And the way dinkum has changed over the years is typical of the way English regional dialect words have been incorporated into Aussie English. Dinkum went on meaning 'work' for some years, so that in Robbery Under Arms (1882) Rolf Boldrewood has his central character Dick Marston say: 'It took us an hour's had dinkum to get near the peak.' (He's talking about the hard work of driving a mob of cattle.) Later dinkum took on the adjective 'fair'—with the notion of 'a fair day's work for a fair day's pay'. Then this notion of honesty took over and became the main meaning of the word. Today dinkum means 'true; honest; genuine'. But it started life as a Derbyshire dialect word.

Edward Peacock, A Glossary of Words Used in the Wapentakes of Manley and Corringham, Lincolnshire (1877) lists a meanings for ding and ding in:

Ding, a blow. 'I'll fetch thee a ding ower th' head, if ta says another wod.'

Ding, v. Dung, pt. t. (1) to strike, to dash down. 'Ding them wedges in, that'll rive her;' said to a man splitting ash-tree roots for fire-wood. (2) To talk much, to gabble. 'Don't ding so, bairn.' (3) To surpass. 'Well, this telegraph dings all I ivver heard on.'

Ding in, v. (1) to drive a stake or any such thing into the ground. (2) To force knowledge into the head of a stupid person. 'I've tell'd thee ower an' ower agëan, an' I can't ding it in to thee.'

The same glossary lists special local meanings of "fair":

Fair, (1) level, even. 'Th' table doesn't stand fair.' (2) Easy, plain. 'It's fair enif to do noo one's tell'd hoo.' 'Lincoln's minister's fair to see fra Barton field. (3) adv. Easily. 'We can see Kidby lamps very fair to-night.'

In aggregate, Peacock's entries tend to bolster Partridge's suggestion as to the source of dinkum.


'Dincum' and 'fair dinkum' in the wild

A search for the word dinkum in the National Library of Australia's Trove database yields a first occurrence in the form of "fair dinkum" (in quotation marks) in an item titled "Morning Gallops" in the [Sydney, New South Wales] Evening News (August 23, 1879):

The work on Randwick this morning was almost of a purely sensational nature and everything that put in an appearance did really serviceable work. The following are the principal items:—Mabel, the up-country mare, was sent what is known as "fair dinkum" over two miles, of course outside the hurdles, in 3min 49sec, and this eclipses anything yet done this season. A rush was then made on to her for the Metrop., and she was well supported both right out and in doubles.

This is followed five months later in "Turf Notes" in the Maitland [New South Wales] Mercury (January 15, 1880):

On Friday morning the ball was set rolling by Black Swan cantering three miles slowly. Her companion Soothsayer proved himself a good horse over a mile and a quarter, but he has failed to come up to the expectations of his backers. Secundus is quite fresh from his spell ; he was sent one mile steady by himself, and in the next picked up Soothsayer, Lowlander, and True Blue, and the quartette finished together at a strong pace. True Blue gives promise of doing something this meeting, as he put Lowlander through on Saturday morning over a mile, doing the fair "dinkum" with whip and spur.

And then, five days later in "The Northern Jockey Club Races" in the same newspaper (and involving some of the same horses):

On Saturday morning I made all possible haste to get to Rutherford in time to see some swallow-catching, but I was too late to catch some of the "birds," who had winged their flight at half-past three. The Swan had finished her work, and to me she appeared jaded. I was just in time to see Soothsayer and True Blue doing the fair "dinkum" over a mile and a quarter. That cleverest of horsemen, Hinks, piloted Soothsayer, who was not asked to extend himself by the brown Kelpie, and came away quite comfortably at the finish. The time was nothing wonderful.

The problem for Kel Richards is that all three of these instances of "fair dinkum" reached print before Rolf Boldrewood's novel containing "hard dinkum" did. And it is not at all clear that the hard sprint under "whip and spur" that the horse-racing term seems to envisage emerged from a notion of "fair dinkum" as "a fair day's work." Indeed the reverse seems quite possible—that "fair dinkum" began in a sense similar to "hard labor" and only later softened to mean something closer to equitable labor.

In any case, almost two years after the last of the three early horse racing examples, the Sydney [New South Wales] Morning Herald (December 27, 1881) listed a 14-foot canvas dinghy named Fair Dinkum competing in the second race (for crews under 21) of the Pyrmont Regatta. By 1886, the expression was showing up in want ads, such as this one from the Sydney [New South Wales] Morning Herald (December 30, 1886):

RESPECTABLE HOUSEMAID wanted, 13s weekly, servants kept. Fair Dinkum, Herald Office.

"Fair dinkum" appears once again in the context of horse racing in "Sporting," in the [Hay, New South Wales] Riverine Grazier (May 24, 1887) but the sense of the phrase here seems quite different from the earlier "hard run" sense:

It's no use denying it; I am a prophet. When Friend Hills took the secretaryship of the Hay Jockey Club I at once put my garments and prophesied straight away—fair dinkum—that Hills would do it, and he has done it. Never in the history of the Hay Jockey Club has there been such a nomination—166 in all, just the neat amount of £166.


Conclusion

Even though the three earliest matches for dinkum that I've been able to locate are from New South Wales, it seems likely that the term originated in England and migrated to Australia, rather than the originating in the colony and migrating to the mother country from there. The idea that dinkum originated as ding in in Lincolnshire (or nearby) dialect seems defensible to me.

More mysterious is whether "fair dinkum," like unmodified "dinkum," originated in England or whether it first emerged in Australia—specifically, New South Wales—and whether it arose in this form in the milieu of horse racing. [[Followup (6/13/2018): On this point, I am persuaded by Phil M Jones's excellent find of an entry for "fair-dinkum" (meaning "that which is just and equitable") in Edward Sutton, "North Lincolnshire Words" (1881) that the phrase originated in England and that the meaning shifted (probably in Australia) among horse-race enthusiasts to mean a hard ride or stern test—but that the old Lincolnshire sense of the term subsequently reasserted itself in Australia, suggesting that immigrants from outside the horse-racing milieu never stopped using the term in its earlier sense.]]

Clearly, the meanings of the terms dinkum and fair dinkum have evolved considerably since 1879, when we find the first print example of it, in Australia; but the impetus for those changes remains shrouded in obscurity.

Solution 2:

Found an older reference, allegedly from 1881:

Fair-dinkum, that which is just and equitable

A more reliable source than a Google snippet, showing the same text:

Original Glossaries (1881) on page 117 (which shows as page 132 in the scan). The date MDCCCLXXXI is clearly shown on page 7 of the scan.

The definition comes from the North Lincolnshire Words section of the publication, which bears out the suggestion on etymonline that it is "perhaps connected to Lincolnshire dialect"

EDIT (13-Jun-2018)

The same definition is also included in the North Lincolnshire Glossary section of "A Glossary of Words used in the Wapentakes of Manley and Corringham, Lincolnshire", the title page of which is dated 1877, although the preface is dated 1876.

Solution 3:

Nottingham Evening Post 23 Feb 1882 p 2 Report of North Lincolnshire Conservative Party meeting discussing the forthcoming Bribery Bill, Mr Richard Hall said that 'in all these things he always thought there should be fair dinkum to all classes of people'. Origins in Lincolnshire are very convincing.

Solution 4:

Fair dinkum can be found earlier than the OED's 1888 dinkum, and was used first in horse-racing. The OED has fair dinkum dated to an 1888 book:

1888 ‘R. Boldrewood’ Robbery under Arms v, It took us an hour's hard dinkum to get near the peak.

But this same story was published in an 1882 newspaper and refers to driving cattle:

It took us an hour's hard dinkum to get near the Peak. Sometimes it was awful rocky, as well as scrubby, and the poor devils of cattle got as sore-footed as babies— blood up to the knee, some of 'em ; but we crowded 'em on ; there was no help for it.

[Fiction. Robbery Under Arms. CHAPTER IV. The Sydney Mail and New South Wales Advertiser (NSW) Saturday 22 July 1882 p 126.]