What exactly should I add in an extended and revised version of my research paper?
In my experience, extended versions most typically contain three classes of new information:


More extensive prose and examples to explain, discuss, and otherwise clarify the material presented in the original paper.  Conference papers are sometimes rather haiku'ed due to page limits.
Important details omitted from the original paper due to length.  For example, a discussion of the key points of an algorithm may become a full presentation of its details, and a proof sketch may become a proof.
Extension work, either enhancing evaluation or extending the set of material studied, as suggested by the original paper's future work, feedback from the reviewers, questions raised in the conference talk, etc.


Some combination of these is almost certainly the right sort of material for your extended paper, but which combination exactly is something that only you, your collaborators, and your advisors are in a good position to determine.