I suppose there are several methods.
For native executables, I think one would create a template program (already compiled), where there would be some dedicated pieces of a data section that are purposely located at the end of the executable. This would allow easy manipulation in order to insert a payload (and it's length and/or other parameters) without having to recompile the self-extractor. One could also make a self extractor that relies on a system-available compiler, but not everyone has a compiler installed.
Self extracting scripts are easier. One could place a payload after all of the script code, and the script itself would not allow the payload garbage at the end to be executed. Depending on the scripting language, you may need to make the payload compilable if the script is precompiled, and in this case, you could use the languages commenting mechanism to achieve this. Using a binary encoding method (i.e. base64, uuencode) might be appropriate in this case. At the end of the script and at the beginning of the payload, a signature is usually placed, so that the script can detect where the payload starts.
Here's a very simple example of a self extractor for a shell.
CODE
#!/bin/sh
ME=$0
echo "Extracting file file.tgz"
if [ ! -f $ME ]; then
ME=`which $0`
fi
if [ ! -f $ME ]; then
echo "Unable to find myself in the file system!"
exit 1
fi
# Extract myself
cat $ME | sed '0,/[B]EGIN_PAYLOAD/d' | uudecode -o - | gunzip | tar xf -
echo "Extraction complete."
exit
# BEGIN_PAYLOAD
begin 644 files.tar.gz
M'XL(".Y4;D@``V9I;&5S+G1A<@#MT4$*PC`0A>&L>XJ<0">=I#E/P!:L1<1$
M\/BVBJ`+<145_+_-,+.9!Z_TN;1K4Y7,8@C+=#'(X[PSSHFJ#Q*TF^]1-!H;
MZL:Z.>62CM9^XM4O*M?^A^W4K\JYU/FQ%-QY_[I_U:7_-HJ/ZM6(D^"\L5(G
MSK,_[S^GS6X:QKP9IC$UARGM2Y/F+>7FV]$`````````````````O'$!-*13
%TP`H````
`
end