You should fork the project, yes. However, this does not mean you need to clone the whole stuff again locally.
Explanation: a simple way of looking at a git repository is a graph of commits (it is directed and acyclic but that is irrelevant for this discussion); and all nodes of this graph, ie the commits, have a unique identifier across all git repositories in the world. As to branches, they are just symbolic references to a commit (in git parlance, a branch -- or a tag -- is called a refspec).
Also, you are never linked to a remote repository in any way. The only thing you are really "linked to" is the commit graph. A remote repository just happens to have a set of refspecs (branches, tags)... pointing to a commit graph, which they also have -- nobody likes dangling references. When you clone a repository, you get the commit graph (and associated trees) and the set of refspecs (ie branches, tags). A refspec points to a tree. And that's about it.
This means the following:
- you have the original github repo: a graph of commits and associated trees, a set of refspecs;
- you have cloned it locally: the same graph of commits and associated trees, the same set of refspecs;
- you have committed stuff locally: you have added upon this graph and associated trees, and added a new set of refspecs.
OK, now do the following:
- clone the original repo on github: the same graph of commits and trees as the original; the refspecs are here, only preceded with the remote name, which is
origin
by default. And what now?
- on your local repository, add your fork as a remote;
- push to that fork (this will push the refspecs, and trees);
- submit a pull request.
Adding your fork as a remote is as "simple" as:
git remote add myfork git@github.com:youruser/theproject
Push your refspec (branch) to it:
git push myfork mybranch
And then submit a pull request to the original author.
It should be noted that in theory, you can add a remote to a git repository which has no relevance at all with the "original" repo: this is simply that the two commit graphs will be completely disjoint from one another -- however, the use cases for this are rare