Perfect timing for this thread! I've spent a ton of time lately working on a project very closely related to this (one of the reasons I'm behind on my JVM for Prizm, incidentally

), so I hope I can answer your question to some extent. Also, please use my post in buttsfredkins' thread as guidelines, not hard "You
have to implement <feature>" for a CAS. I've been learning a lot of CAS theory lately and I realize just how ambiguous a lot of my statements in there really are.
First of all, computer algebra systems are difficult to write because they have to do a lot of things and there's a lot of math underlying them. If you don't have a firm mathematical background, you're quickly going to find yourself in over your head once you try doing research on how to write one. Accordingly, make yourself familiar with Wikipedia and
Wolfram MathWorld. They'll be your best friends when you're struggling to understand say, Grobner Bases.
Also, remember that almost everything you need to write a CAS has already been discovered and published. When in doubt, Google. Another excellent source that I refer to for all kinds of things is
Algorithms for Computer Algebra by Geddes, Czapor, and Labahn. It basically takes you through many of the most useful (and difficult!) algorithms in any CAS with good descriptions, excellent mathematical underpinnings, and even pseudo-code. If you can't get your hands on it, I believe certain member(s) are willing to make it available.
Also, learn the distinction between Numerical packages and Computer Algebra packages. CA packages deal with symbolic manipulations of relations in order to get a symbolic answer (e.g. ∫2xdx → x^2+c). Numerical packages deal with evaluating and approximating relations to get a numerical answer (e.g. Lim (x^2) as x → ∞ = ∞). Both types of packages are useful for solving certain types of problems that the other type has significant trouble solving. Very few "CAS" packages fail to include numerical functions on account of this.
As for a general idea of how CASes work...
----------------------------------------------------------------------------------------------------
| |
| ------------ -------------- --------- ------------------------- |
-->| Text input |---->| Tokenization |---->| Parsing |---->| Decide algorithm to use |--- |
------------ -------------- --------- ------------------------- | |
| |
---------------------------------------------------------------------------------------- |
| |
| --------------------- ------------------- --------------------- -------- |
-->| Apply manipulations |---->| Evaluate function |---->| Make output legible |---->| Output |-->--
--------------------- ------------------- --------------------- --------
These steps are generally combined in various ways in a real CAS, but I think it helps demonstrate the process a bit more clearly.