The AVI container format does not support embedded (muxed) subtitles at all - it only supports hard subs, which requires re-encoding the video with the subtitles actually in each video frame.
To have muxed subtitles you need to use either the MKV or MP4 container formats, depending on the subtitle format.
Your AVI files can be remuxed into either container, again depending on the video and audio codecs. See Comparison of container formats on Wikipedia for compatibility tables.
I have found that MKV supports far more combinations than MP4
The MKVToolNix package is available for Linux and will do everything you need
For MP4 the tool to use is MP4Box
If you need more info on the difference between a container format (e.g. AVI, MP4, MKV etc.) and a codec (e.g. DivX, Xvid, H.264 etc.) then Digital container format and it's linked articles is a good place to start.