One approach is to determine the maximum error you're prepared to live with, then replace the sin() function with a series of straight line segments; specify fixed values at fixed points then for intermediate points use linear interpolation. You can eliminate three quarters of the data you would otherwise need for a full sinewave by using symmetry; define values for 0-90 degrees then e.g. sin(180+x)=-sin(x); sin(-x)=-sin(x) etc.

e.g.1: a simple straight line from (0,0) to (90,1). sin(45)=0.7071, but our approximation is 0.5, which is a huge error of .2071. But this will be really fast and could in certain circumstances be acceptable (for example if we're generating a 10kHz sound wave and will be chucking the output through a 20kHz low pass filter such as a human ear).
e.g.2: two straight lines from (0,0) to (.5,.7071) to (90,1). sin(22.5)=0.3827 but our approximation is 0.3536 (off by .0291). This is considerably better for a lookup table of only 2 values (because we can include the endpoints in the code)
e.g.3: three straight lines from (0,0) to (30,.5) to (60,.8660) to (90,1). sin(15)=0.2588 and our approximation is 0.25 (off by 0.0088 which is less than 5%).

You can use the same lookup table for cos because cos(x)=sin(x+90).
The symmetry of cos around x=0 (cos(-x)=cos(x)) might make it better to define the values for cos then sin(x)=cos(x-90).

Also you can avoid compounding errors by leaving the calculation until as late as possible. If you have, say, a 20-step calculation where sin() is called at step 1 and each step adds a possible x% error, then the error present in the sin replacement is compounded by (20^(1+)x)% (I think, anyway, it's x% compounded 20 times; use same calculation as compound interest). However if the sin function can be left until later, say until step 10, then the error is only compounded (10^(1+)x)%.