Use Selection mode for the feature layer. Set your symbol using Layer.setSelectionSymbol(symbol). If you have a complex symbology, set the renderer instead and leave the selection symbol blank.
There are two ways to go about the next part.
Use the checkboxes to composite a complex query. For example, if each feature has a unique identifier (call it IID), then you query will be:
Where the list of IDs is built from all the checked check boxes. jQuery can be very effective in building this list. Whenever a checkbox is updated, you want to execute
Use simple queries to add and remove each feature individually as boxes are checked or unchecked. When a checkbox is checked, you use:
When a checkbox is unchecked, you use:
As you add features to the current selection (or create a new selection) those features will be displayed. As you remove them, they will be hidden. Since selectFeatures() will execute client side if possible, this actually operates very quickly.
Try this sample from ESRI. It sounds like exactly what you are asking for.