I'm a novice at military affairs, but here goes nothing.
Firstly, in response to the OP:
Surely German forces between June of 1940 and spring of 1941 would have easily finished off the British in North Africa
That's assuming that the British could be 'easily finished off' in North Africa.
Dunkirk aside, the British proved to be a formidable foe
both to the Italians and their German allies, but especially to the latter.
Heck, without German intervention, the British very well could've advanced further into Libya than they already had - the arrival of motorized and armored Germany army units bolstered an Italian force lacking in motorized as well as armored formations.
It was only, IMHO, the intervention of the Africa Corps that prevented a total Italian defeat, and even then the Allies proved resilient in the face of renewed Axis offensives - able to face Rommel with equally good commanders (such as Montgomery)
So no, I don't think that the British could be 'easily finished off' in North Africa simply by assuming that German forces entered the Mediterranean theater earlier than IOTL.
In all possibility, this would have been a feasible goal for Italian and German planners - but I'm not an expert on WWII naval affairs so I can't say for certain that it would succeed.
...taken Gibraltar (although that would have been somewhat problematical)
Exactly. Even with Franco joining the Germans, its not simply a matter of marching into Gibraltar with one's army as in a real time strategy game.
Furthermore, why take Gibraltar when seizing Malta would require less resources, less diplomatic wrangling, and would be closer to the Brits' military operations. Malta falling, especially considering its literal central location in the Mediterranean Sea, would deprive any British force sailing through the strait of Gibraltar of a key naval base situated between the Gibraltar strait and Gulf of Suez.
So, IMHO, the question of whether or not the Nazis should launch and assault on Gibraltar, faraway from the main theater of operations and hence a logistical nightmare is a moot point.
...By turning the Mediterranean Sea into an Axis lake...
Possible, esp. after seizing Malta, but not a near certainty owing to the Axis powers' inferiority in naval power when placed in comparison to the British Royal Navy.
Assuming that the Germans make it that far - the British would probably fight like hell esp. if the Germans got past El Alamein or some similar notable mark. Cairo and Alexandria wouldn't go down without a fight, and even then the British could simply retreat across the Suez and possibly even launch a counterattack against a greatly overextended Axis force hard pressed to hold down at the very least coastal Egypt - not to mention the recently conquered cities of Cairo and Alexandria.
Expect some form of guerrilla warfare as well on top of said logistical problems (or hellholes, depending on who one asks) - I might be wrong on this but something along the lines of the famed Desert Rats.
...German forces in Palestine
IMHO, I don't think that the Germans would ever make it that far, at least not without investing much needed time, men, resources and such that they would have to divert forces from northern France (necessary to prevent any future Allied attempt at opening a new front in Hitler's backyard) and the east (primarily Poland).
Without a southern front, that might have freed much of the German occupation force in Greece, Yugoslavia (etc) for use in the invasion of the Soviet Union
That's assuming, given the butterfly effect, that the Germans even do end up invading the USSR. They would have significantly less troops positioned on their border with the Soviet Union, while the laser-like focus on the Mediterranean would have brought into question the feasibility of picking a fight with Stalin when a good portion of the German air force, navy, and ground force would inevitably be committed to a hellish campaign fought across vast deserts spelling disaster for the attackers' supply lines.
In short, once a Mediterranean strategy IMHO was chosen, Hitler whether he liked it or not would not be able to launch Operation Barbarossa - at least not to such a great extent as IOTL.
Concerning ObsessedNuker's point in relation to Tunisia:
...Because those supplies [from Tunisia] have to get from Tripoli to the front.
As he goes on to say, said influx of supplies aren't worth a damn one the Germans push onwards to Alexandria and Cairo.
Given the poor quality of the roads leading from Tunisia to Tripoli, assuming that they could be repaired or at the very least made somewhat passable, said supplies once headed from Tunisia to Tripoli would reach the front line way too late - esp. if said line stretches deeper and deeper into Egypt.
Heck, the Germans might as well not bother with Tunisia (which would only suck in more men, resources, aircraft, etc.) and resort to resupplying Tripoli instead from the sea or by air - nonetheless, the fact of the matter is that logistically the Germans won't be and shouldn't be able to cut off the Canal, advance into Palestine, and the whole bit.
The whole affair is reminiscent in terms of grandiose wishful thinking on Hitler's part as the ill fated Ardennes Offensive - too much territory to cover, too much of a determined Allied force to contend with (navy, air force, and land army all taken into account), and too much of a strain on logistics that such a massive plan to decisively end the war in the Axis' favor would (and did, in the case of the Ardennes Offensive) peter out.