This is a collection of insights that I found over the years of writing and reviewing theses. It doesn't aim to be exhaustive, nor does it try to be the final authority. Just some advice that I would give to my past self, and maybe it'll be useful to others.
What are the jobs of the individual chapters?
Introduction: Motivate the problem, outline the project (for more details, see below).
Background: Give a high-level summary of any topics that someone working in a different field of CS may not be deeply familiar with. This can be protocols, tools, or the current state of the art for whatever you are working on. Include important terminology or common mathematical definitions. Domain experts will usually skip this when reading your thesis. To avoid losing these people later on, make sure your thesis adheres to common conventions in the field and perhaps re-introduce important definitions where they are used.
What comes next is up to your specific project. Basically, this is the technical part of the thesis, and usually also the one that comes most natural to write. For many projects, a structure of "Overview" -- "Implementation" -- "Evaluation" -- "Analysis" works well.
Related work: Give a systematic overview, focusing most of the space here on the approaches you are "competing" with or building upon. Make sure it is clear to the reader how you are positioning yourself: What are the limitations of other approaches? How do they compare to yours (or perhaps they are orthogonal)? But make sure not to get caught up in these; also include different approaches to similar problems and similar approaches to different problems.
Conclusion: State the goals you have achieved again (this is usually done 3-4 times in total: in the abstract, the intro, the evaluation, and here), but very specifically. "Future Work" is code for "things I did not have the time to do", put anything in there even if no one actually plans to do it in the future. If there are enough points, put them in a separate section (i.e., §7 is "Conclusion", §7.1 is "Future Work").
Where should I start writing?
Related work and background are good places to start. This is a good time to revisit the work that is related to your thesis anyway, as you need to relate your results to the existing ones (e.g., in the introduction, conclusion, or the abstract). As you will probably have read most relevant work somewhat in detail already, it should be enough to just make some brief passes for most papers. Moreover, writing the background first will allow you to better adhere to conventions in your field (i.e., use similar notation). After that, I usually like to write the main part and do the introduction toward the end (or when I have a really productive day, because this is usually quite a tough piece of writing).
How to write an introduction?
The introduction needs to cover four basic questions:
Why is the problem (domain) important? This is usually one paragraph that provides a very general introduction to the topic at hand and broadly introduces your problem. Do not be afraid to cite "less scientific" things like news articles here to support your point. Make sure that after this paragraph, any interested reader (even non-experts) will be convinced that this problem is important.
Why has it not been solved? In research, it is not just your task to find a solution, but also to identify problems. Make sure you state what issue you are tackling and why existing solutions (if there exist any) are not yet enough. You can draw from your Related Work section
What is our idea? Give some very high-level intuition about your key idea, and why you expect your approach to improve the current state of the problem.
What do we contribute? Here, I often find it best to provide an explicit list (bullet points) of contributions with concrete, verifiable claims. Example:
How to write an abstract?
I usually like to write this at the very end. The abstract gives a very brief overview of the situation, your main idea, and concrete results. If you have any numbers or interesting results, add them here already.
Where do I put the "Related Work" section?
There are two options here:
Before the conclusion. This is the best option in most of the cases. However, do not hesitate to mention existing work earlier in your thesis (especially in the introduction).
After the introduction. This can be a good choice in some cases where your project is heavily based on existing work and you need to be clear what aspects you are extending.
What are the most important parts?
Your writing matters most in the introduction. Make sure this is as polished as possible, as it sets the tone for the rest of the thesis. In research, one of the most important parts is always having a clear motivation and framing for your work and explaining your key idea(s) that expand on existing work. Also, readers will usually refer to this section in order to see what exactly it is you are contributing to the research community.
Every paragraph should have one clear, minimal purpose. For important parts like the introduction, I have found it helpful to keep a comment in the source code above each paragraph with a couple keywords to outline its purpose. This makes proofreading more efficient and helps you maintain the section's structure while copying things around.
Reverse outlining is a good technique to check if you have followed this principle: Open a second document and copy the most important sentence from each paragraph into the new file. If you do this (strictly one per paragraph) and the resulting document still brings all your points across, your structure is good.
Some frequently useful tips:
The Chicago Manual of Style provides many more recommendations for stylistic choices and is kind of the de-facto standard for nitpicking.
Use LaTeX and get a memoir-style thesis template (e.g., from CADMO).
I recommend the cleveref package to automatically create references in the correct format (e.g., "in Table 1").
It is also a good practice to create commands for terms / symbols that you use often, especially since you might end up renaming them once or twice over the course of the writing (I've been there).
That way, just a single line change is enough to fix your entire document.
A related useful package is acronym, which automatically makes sure that acronyms are written out the first time they are used.
To keep things organized, it helps to make a separate file for every chapter (combined using \input{}).
Also, I prefer to have packages, layout settings and general definitions in separate files.
For version control systems, I find it useful to stick to "one sentence per line" (enable soft wrap in your text editor so you can still see things). This allows you to track your changes much more efficiently (changing a word in a sentence does not produce a paragraph-long diff anymore) and will definitely come in handy when collaborating.
If you ever need to write a paper, it's basically the same, but with two columns.