I once heard a shiur which quoted a gemarah (I think) about two trees. One of the trees was uprooted and taken elsewhere and the other tree started to get sick. The explanation was that the trees were in love. I may be off on some of the details here. What is the source for this story?
Sounds like you are referring to this
מדרש רבה במדבר פרשה ג פסקה א "ר תנחומא מעשה בתמרה אחת שהיתה עומדת בחמתן ולא היתה עושה פירות והיו מרכיבין אותה ולא עשתה פירות אמר להם דקלי תמרה היא רואה מיריחו והיא מתאוה לה בלבה והביאו ממנה והרכיבו אותה מיד עשתה פירות כך כל תאותן וצפויין של צדיקים הקב"ה
the gist is that there was a tree which would not produce fruit and they were told that it was in love with a tree in Yericho which they brought and grafted with it and it bore fruit.
The lesson of the story is that just like this tree was in love with the other tree to such a great degree, so is Hashem in love with the righteous.
This story is also brought down in מדרש רבה to Parshas לך לך, in פרשה מא פסקה א.
The quote is from Breishit Raba and Bamidbar Raba. An agricultural clarification: Date trees need a male tree, which produces pollen and a female tree which when pollinated produces the dates. One cannot "graft" anything onto a date tree. Physiologically, it doesn't work. What was done to pollinate was to take a piece of the pollen pod and stick it at the top of the female tree so that the flowers would be pollinated. The Medrash tells us that a pollen pod from Yericho was used. מרכיבין in this case means "stuck in the top of the tree". It is temporary, not permanent as a graft would be.