Your confusion may arise from the fact that while there is an idiomatic phrase to do with (meaning concerned with or related to), these (both of your examples) do not use that idiom, but rather the three words that happen to be in the same order.
In both of your examples, we have one of the more common usages of do, "To perform, execute, achieve, carry out, effect, bring to pass." (OED, sense 4) It is used in its infinitive form with with as an adjective modifiying $300 million (or money, in the second example), which is the direct object of gives (Bill Maris is the indirect object).
We can reword the sentence a couple of ways that break up the phrase, but keep the meaning. First, simplify the sentence for clarity:
Google gives Maris money to do with what he deems best.
These would be equivalent to it:
Google gives Maris money with which to do what he deems best.
Google gives Maris money. Their intent is that he do with it what he deems best.
Google gives Maris money. Their intent is that he do what he deems best with it.
Google gives Maris money. Their intent is that he use it as he deems best.
For comparison, you could construct a similar sentence that does use the phrase idiomatically (in the related to sense):
Google gives Maris money to do with his performance in the previous year.
Google gives Maris money to do with the need for new equipment.
Google gives Maris money that, unofficially, is to do with certain photographs he possesses of board members.
As you can see, this is a totally different meaning of to do with than in the original sentence. Notice that the objects of to do with in these sentences are not actions or implied actions but things or ideas (related to money), as opposed to what he deems best, which is an implied action (that Maris will do).
On the other hand, we could construct similar sentences that use infinitives other than to do to modify money.
Google gives Maris money to give to the poor.
Google gives Maris money to wallpaper his office with.
Google gives Maris money to throw out the window.
Google gives Maris money to fold into little swans.
I hope I've correctly understood the issue; I'm making assumptions based on the fact that you used the "idiom" tag here.