First let's start with the simple answer: "pull" starts by invoking "fetch". It then performs either a merge or rebase depending upon various "git config" settings and CLI options you can pass to git pull.

Now let's pop the hood.

Git commit history is represented by a graph. Typically each commit has a pointer to a single parent. When history diverges and needs to be merged, a merge commit is created which has two parents (it can have more than two but such a commit is extremely atypical). The first commit obviously has no parents and is also called a root commit.

Okay, so we've got a history of commits pointing to each other in a directed acyclic graph. Now we want to traverse that graph with "git log". Where do we start? This is what branches are, a mapping from a name to a particular commit. Git stores the branch names under .git/refs/heads. Go look. These are just files whose names are the branch names, and whose values are the SHA-1 of a particular commit. (For performance reasons, git will occasionally remove the files and instead use .git/packed-refs. But again this is a file you can go cat.)

Now, there are two types of branches: 1) local branches; 2) remote branches. Local branches are just the names (those things under refs/heads) which git updates whenever you create a new commit. Remote branches are the things which git updates when you perform a git fetch. That's it.

So a fetch operation examines a remote repo's local branches (refs/heads), examines the corresponding remote branches in your repo (refs/remotes/<remote_name>), pulls over the differences, then updates your remote branch to match the remote's local branches. It does so according to .git/config with a section that looks like this:

[remote "origin"]
url = https://github.com/gitster/git.git
fetch = +refs/heads/master:refs/remotes/origin/master

That "fetch =" line tells git what to do when you invoke "git fetch" or "git fetch origin". It says to update your repo's refs/remotes/origin/master to match refs/heads/master in gitster's repo on github. The "+" at the start means to force it to happen even if the remote end has been rewritten (that is, the remote master's history does not "contain" refs/remotes/origin/master on your end). When you invoke git fetch you can see this happen in its output:

From https://github.com/gitster/git
52a3e01..edca415 master -> origin/master

Well what happened here? Fetch examined refs/remotes/origin/master in my repo and refs/heads/master in gitster's repo, pulled over the commits I was missing, then updated my refs/remotes/origin/master (aka origin/master) from 52a3e01 to edca415. So "git log 52a3e01..edca415" will show me exactly the commits that fetch just brought over.

You'd typically perform a git fetch on its own so that you can then do something like "git log master..origin/master" which tells git to show you all the commits that are in refs/remotes/origin/mater but that are NOT in refs/heads/master, i.e. exactly those commits you either need to merge in or rebase upon.

So that's fetch.

Git pull then invokes either merge or rebase. To talk about these let's add some history.

Pretend your local repo started as a clone. The remote repo ("origin") has a single branch, master, and at the time you cloned it there was a single commit on master, A. So your local repo after the clone:

refs/heads/master: A
refs/remotes/origin/master: A

Now you create a new commit:

refs/heads/master: B
refs/remotes/origin/master: A

Someone else pushes a new commit to the clone and you fetch that commit:

refs/heads/master: B
refs/remotes/origin/master: C

Now we have a case where history has diverged. Two people have created commits, both which have the same parent commit A, and we need to tie these both into master. Let's do it with a merge first:

refs/heads/master: D
refs/remotes/origin/master: C

But what is "D"? D is a merge commit with two parents, B and C. And because D "contains" C, you can push it to the remote repo, updating refs/heads/master in the remote repo.

But what if instead you want to rebase?

refs/heads/master: B'
refs/remotes/origin/master: C

This has linearized history. B' has a single parent, C, whose parent is A.

Similar to creating the merge, you can push B' to the remote repo because B' contains C (unlike the original B). The rebase operation "rewrote" refs/heads/master, dropping the original B which had A as its parent and replacing it with B', which has C as its parent. Your original B is still in your repo btw, and will be there for some time until "git gc" removes it. You can find the original B in your ref log.