The first source for that expression is the Alshich - first published 1593, but likely said significantly earlier. The concept is older. According to Tanya it means that the soul uniquely feels itself inseparable from G-d, more so than other things that exist in creation.
As far as I know, the first source for this specific expression of the idea is in the Alshich (first published in 1593, but based on drashos he would have given over time), in a few places. One reference is here. The Kli Yakar (published 1602) also has several mentions of it, one is Bereishis 1:31 and another is Bereishis 9:20.
As far as I know the first appearance of the famous addition of the word "mamash" that is known from Tanya at the beginning of chapter two is in a sefer called שפע טל, by Rabbi Shabtai Shefel Horowitz published in 1612. In the first paragraph of the introduction he writes:
ידוע שהנשמות של אומה ישראלית הם חלק אלוה ממעל על זה רמז הפסוק כי חלק ה' עמו ר"ל חלק ממש כחלק שנחלק מאיזה דבר הוא שוה ודומה בעינו לאותו דבר שנחלק ממנו
It is known that the souls of the Jewish nation are a "portion of G-d above." On this the Posuk hints "A portion of G-d is with him" meaning an actual part [as opposed to an idiomatic statement] that was taken from something - it is equal and similar in its type to the thing it was taken from.
It is certainly understood from the language "it is known" that the concept is not new even at that point, even if the association with this particular wording is. (See, for example, the Ramban on Bereishis 2:7 where it says that the soul is רוח שם הגדול - which is in line with how Tanya explains it).
The author of the שפע טל is the nephew of Rabbi Yishaya Horowitz, better known as the Shaloh HaKadosh. In his Sefer (Part 1, Bais Chachma towards the end) he says "You already know the Neshama is a Chelek Elokah Mimal". This was printed later than the שפע טל (well after the Shaloh HaKadosh had passed away).
In terms of what it means, this is explained at some length in Tanya Part 1 Chapter 2 as well as Part 3 Chapter 4. That latter explanation is more direct and to the point: The soul is G-dly, a part of G-d's Name. It is a metaphor that expresses the idea that there is a qualitative difference between the soul and other spiritual creations like angels. Lessons in Tanya succinctly sums it up:
This, then, is the difference between souls and angels: Souls derive from the innermost aspect of G‑dliness, the Tetragrammaton, while angels are rooted in the external aspect of G‑dliness, the Divine Name Elokim
What characteristics of the soul also characterize Havayah, the Four-Letter Name of G‑d, and thus indicate that the soul is indeed a part of that Name? In answer to this question, the Alter Rebbe now explains that just as the Ten Sefirot are included within the Tetragrammaton, so, too, there are ten corresponding faculties that are intrinsic to the soul.
So to sum it up in a sentence, although all creation comes from G-d, creation in general feels itself to have an independent existence, whereas the soul spoken about here does not - it recognizes its inseparability from G-d.
In Tanya the Alter Rebbe notes an observable expression of this phenomena - many Jews throughout history who were emphatically not observant to any serious degree, and simply didn't do much about their Judaism in their day to day lives still gave up their lives rather than undergo forced conversion. This is an expression of the soul's refusal to be separate from G-d above its own existence. [This is sometimes misunderstood to mean that martyrdom is uniquely Jewish. It is not at all, but the point being a martyr is someone you would expect to have a high dedication to their cause prior to the circumstance where they chose martyrdom, rather than it coming seemingly out of nowhere].
Basically, as I heard Rabbi Elimelech Zweibel explain it, the problem with the metaphor of the שפע טל above is that when it comes to something physical, you can say that part is taken, and moved to another place. Take a cup of water out of the ocean, and bring it to your house. You now have a piece of the ocean in your house.
However, in these spiritual concepts of higher angels, lower angels, etc. they are not physical. You cannot "move" them to a different place. When something is of a lower spiritual stature, it is in the lower world by definition. If you take something spiritually higher and lower its spiritual status, it is inherently lower. So how can anything spiritual retain that higher world aspect and still come down into lower worlds.
For this the Alter Rebbe gives two metaphors. One is speech vs. blowing, the other is fathering a child. The point of both is to illustrate something descending into a lower state while maintaining qualities of its higher source, different from other things that come from the same source but do not maintain that quality.