I have actually never related both words together, but coincidentally, I realized that in germen, "art = Kunst" and "artificial = künstlich", namely people do relate both concepts together. So how is the word artificial derived from art, although they have quite different meaning?
The answer lies in the middle, in artifice.
Artificial is the adjectival form and means something's fake, but artifice specifically refers to using intelligence, skill or a stratagem to outwit someone or trick them into believing something false. The connection to something fake is there but it's shifted to beliefs and connected now to the skill that generated the false belief.
Dictionary.com references an obsolete usage of artifice as "craftsmanship". Art is a specialised craft, often visual. So it's easy to see a connection now between art and artifice, a craft in appearances (deception in the sinister case), and artificial, as something that bears the hallmarks of an artifice.
Artificial also connotes man-made - something to replace the organic. This is something they all share: a painting is a man-made depiction (traditional paintings, landscapes or portraits, stand-in for the real experience) and an artifice is obviously a man-made strategy. This need not be negative, as the idea of "fake" implies, but one can see the relationship between "crafting" something, being fake and getting increasingly distant from the category of "organic". Artificial might be compared to the word superficial in being about surface/immediate perceptions but something superficial implies an emptiness whereas something artificial just has a different composition (but some sense of loss of the "real" thing).
An almost identical analogue of art -> artificial is craftiness. Craftiness both means someone's humble, creative skills with tangible mediums (positive sense) and one's ability to deceive others with a clever strategy (negative sense), i.e. a "crafty person" is cunning because they bend a situation to their advantage like a craftsman, artisan or artist bending their preferred material into a new object. So, a craft (art) is a skill in making something, craftiness is the ability or extent to use that skill and somewhere along the lines craftiness was used metaphorically for mental skill in deceiving others, probably euphemistically.
Dictionary.com and Merriam-Webster both cite the Latin artificum and artifex as etymological roots, composed of the Latin ars, which means skill and is almost identical to the word art (one of the websites explicitly said 'ars' was the Latin word for art). I believe "art" and "craft" had a more interchangeable usage historically as well which lends credence to the parallel above. I'm only speaking for the English here but I imagine the German will follow very similar if not exact lines.
The historical reasons for "art" even having negatively connoting derivatives is perhaps to do with an alternating culture of decrying and celebrating art as alluded. Classical art (realistic portrait/landscape painting) participates in visual appearance and therefore illusion to appear real. We could view this positively or negatively. Historically, painting (as emblematic of art) was seen as lesser to certain intellectual circles; to be an illusion is to deceive which is to deter from or distort the truth, the ultimate good or achievement of the intellect. Plato, for example, argues painting is lesser for having 2 degrees of separation from reality and thus from truth, and this carries throughout the Western philosophical tradition up to the German philosophers (!) 2000 years later saying music is the highest form of art because it's abstract/intangible (so it's intellectual and not "base" or "material" or "illusory"), compared to a painting. In this sense, painting (as emblematic of art) is by its very nature artificial, and so the link might be a lot closer than it at first appears.
But it seems today's view of art is a lot more positive than that. We could say the skill required to make something realistic is impressive enough, much like how we revere classic painters now, or even to say that studying the world in this traditional, visual way of drawing and painting actually unveils truth about objects we wouldn't otherwise get (Leonardo da Vinci argued this in rebuttal to Plato!). Art itself has long-since evolved away from traditional portraiture/landscape to combat various conceptual issues like this (what's real? true? does it matter? etc.) and that's why, on the one hand, it might seem so bizarre to think of "art" as related to "artifical" today, since it's now come to refer to something broader or have a positive sense associated with it that's incongruence with the negative sense of "artificial. Yet, on the other hand, the layperson finds a lot of contemporary art difficult to understand if not outright repulsive, partly because there's a background discussion they aren't privy to, but also because people come to art with different senses and expectations and a lot of contemporary art is deliberately non-traditional in its form. Some people come for the classic realism, to see something pretty to marvel at, which may indeed rely on "deceptive" techniques, while others, I suppose, want a conversation about life and reality and to see something new.
Artifice as "exterior"
Lastly, I had a strong conviction artifice had a specific meaning of "an exterior", but neither of the above sites showed that, nor did a 3-min Google search. This is despite the fact I've heard the expression of "a building's artifice" to talk of a building's exterior, an entrance, facade or image of the building, often pretty. If this definition is valid, it would strengthen my point because I can make the step from art to architecture and artificial via being a decorative enterprise.
It's funny how we can have such a positive reference in the word "art" and then have derivations of completely opposite usage.
As usual, Hippocrates said it already, in Greek, where τέχνη ('techne') means the same as Latin ars:
Ὁ βίος βραχύς, ἡ δὲ τέχνη μακρή, ὁ δὲ καιρὸς ὀξύς,
ἡ δὲ πεῖρα σφαλερή, ἡ δὲ κρίσις χαλεπή.
Vita brevis, ars longa, occasio praeceps,
experimentum periculosum, iudicium difficile.
Life is short, art is long, opportunity is fleeting,
experience is perilous, and judgement is difficult.
Note that this notion of art expands, like PIE *teks, to include all human endeavor.
"although they have quite different meaning" -- but they don't, really.
You could say that art is artificial. They both derive from the latin ars, meaning "art, skill". Artificial derives from the latin artifex, which is comes from ars + fex, meaning "to make".
A piece of art is an artifact, something that is artificial, something that was 'made' with 'skill'.
Appropriately, künst also means 'skill'